Initial

1 files changed, 66 insertions, 0 deletions

diff --git a/DTQuickSort.c b/DTQuickSort.c
new file mode 100644
index 0000000..7434263
--- /dev/null
+++ b/DTQuickSort.c
@@ -0,0 +1,66 @@
+#strict 2
+
+global func SortNumeric(int a, int b)
+{
+	if(a < b)
+	{
+		return -1;
+	}
+	else if(a > b)
+	{
+		return 1;
+	}
+}
+
+global func SortNumericInverse(int a, int b)
+{
+	return -SortNumeric(a, b);
+}
+
+global func QSort(array& data, callback) // WARNING: Can cause stack-overflow with too much data
+{
+	if(callback == true)
+	{
+		callback = GlobalCallback("SortNumericInverse");
+	}
+	QSort_Part(data, callback || GlobalCallback("SortNumeric"), 0, GetLength(data) - 1);
+	return data;
+}
+
+global func QSort_Part(array& data, callback, int left, int right)
+{
+	if(left < right)
+	{
+		// Partitioning
+		var pPos = RandomX(left, right);
+		var p = data[pPos];
+		var tmp;
+		
+		tmp = data[pPos];
+		data[pPos] = data[right];
+		data[right] = tmp;
+		pPos = right;
+		
+		var i = left - 1;
+		for(var j = left; j <= right; ++j)
+		{
+			if(Call(callback, data[j],  p) < 0)
+			{
+				++i;
+				tmp = data[i];
+				data[i] = data[j];
+				data[j] = tmp;
+			}
+		}
+		
+		++i;
+		
+		tmp = data[i];
+		data[i] = data[pPos];
+		data[pPos] = tmp;
+		// -----
+	
+		QSort_Part(data, callback, left, i - 1);
+		QSort_Part(data, callback, i + 1, right);
+	}
+}