diff options
| -rw-r--r-- | DTQuickSort.c | 94 |
1 files changed, 50 insertions, 44 deletions
diff --git a/DTQuickSort.c b/DTQuickSort.c index 8f480ca..caa9369 100644 --- a/DTQuickSort.c +++ b/DTQuickSort.c @@ -1,15 +1,8 @@ -#strict 2 +#strict 3 global func SortNumeric(int a, int b) { - if(a < b) - { - return -1; - } - else if(a > b) - { - return 1; - } + return a - b; } global func SortNumericInverse(int a, int b) @@ -17,50 +10,63 @@ global func SortNumericInverse(int a, int b) return -SortNumeric(a, b); } -global func QSort(array& data, callback, callbackArgs) // WARNING: Can cause stack-overflow with too much data +global func QSort(array& data, callback, callbackArgs) { if(callback == true) { callback = GlobalCallback("SortNumericInverse"); } - QSort_Part(data, callback || GlobalCallback("SortNumeric"), 0, GetLength(data) - 1, callbackArgs); - return data; -} - -global func QSort_Part(array& data, callback, int left, int right, callbackArgs) -{ - if(left < right) + else { - // 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) + callback ??= GlobalCallback("SortNumeric"); + } + + // start of flattened recursive part + var stack = [[0, GetLength(data) - 1]]; + + // stack pointer points to next empty slot + for(var stackPointer = 1; stackPointer > 0; ) + { + var frame = stack[--stackPointer]; + var left = frame[0]; + var right = frame[1]; + + if(left < right) { - if(Call(callback, data[j], p, callbackArgs) < 0) + // 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) { - ++i; - tmp = data[i]; - data[i] = data[j]; - data[j] = tmp; + if(Call(callback, data[j], p, callbackArgs) < 0) + { + ++i; + tmp = data[i]; + data[i] = data[j]; + data[j] = tmp; + } } + + ++i; + + tmp = data[i]; + data[i] = data[pPos]; + data[pPos] = tmp; + // ----- + + stack[stackPointer++] = [left, i - 1]; + stack[stackPointer++] = [i + 1, right]; } - - ++i; - - tmp = data[i]; - data[i] = data[pPos]; - data[pPos] = tmp; - // ----- - - QSort_Part(data, callback, left, i - 1, callbackArgs); - QSort_Part(data, callback, i + 1, right, callbackArgs); } + // end of recursive part + + return data; } |