From 9b5d0a3ddf41e686439dcda1edfe11eee51c3b07 Mon Sep 17 00:00:00 2001 From: Markus Mittendrein Date: Thu, 5 Jan 2017 16:19:56 +0100 Subject: Initial --- DTQuickSort.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 66 insertions(+) create mode 100644 DTQuickSort.c (limited to 'DTQuickSort.c') 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); + } +} -- cgit v1.2.3-54-g00ecf