qsort: clean up the implementation (forward walk rather than backward)

1 files changed, 18 insertions, 36 deletions

diff --git a/impls/qsort.cpp b/impls/qsort.cpp
index 1b644bd..19272c5 100644
--- a/impls/qsort.cpp
+++ b/impls/qsort.cpp
@@ -16,8 +16,6 @@
     (A) ^= (B);    \
   } while (0)
 
-#define TEST_SIZE 10
-
 void print_arr(int *arr, int size)
 {
   printf("{\n");
@@ -28,44 +26,28 @@ void print_arr(int *arr, int size)
 
 void quicksort(int *arr, int arr_size)
 {
-#ifdef TRACE
-  printf("before, arr=");
-  print_arr(arr, arr_size);
-  printf("\n");
-#endif
-  // TODO Optimisation: for small arr_size, a different sort like the bubble
-  // sort may be better, instead of initialising new stack frames.
-  if (arr_size < 2)
-    return;
-  // TODO Optimisation: Use some heuristics to figure out a better pivot than
-  // some constant choice of element.
-  int pivot       = 0;
-  int pivot_value = arr[0];
-  for (int i = 1; i < arr_size; ++i)
+  // TODO: Use a different sort for small enough sizes?
+  if (arr_size > 1)
   {
-    if (arr[i] <= pivot_value)
+    // TODO: Choose a better pivot maybe?
+    int pivot       = arr[arr_size - 1]; // Choose the last element as pivot
+    int pivot_index = -1;
+
+    for (int j = 0; j < arr_size; ++j)
     {
-      if (i != pivot)
-        SWAP(arr[i], arr[pivot]);
-      ++pivot;
+      if (arr[j] < pivot)
+      {
+        ++pivot_index;
+        std::swap(arr[pivot_index], arr[j]);
+      }
     }
-  }
 
-#ifdef TRACE
-  printf("after, arr=");
-  print_arr(arr, arr_size);
-  printf("\n");
-#endif
-  // TODO Optimisation: Use a stack to do this instead of recursion.
-  //
-  // This algorithm is similar to a pre order traversal/dfs, in this case on an
-  // array where left and right partition are children nodes to the original
-  // array node.  Also with recursion there's a real risk for very large
-  // ARR_SIZE of running out of space in the call stack.
-  if (pivot != 0)
-    quicksort(arr, pivot);
-  if (pivot < arr_size - 1)
-    quicksort(arr + pivot + 1, arr_size - pivot - 1);
+    std::swap(arr[pivot_index + 1], arr[arr_size - 1]);
+
+    // TODO: Use a stack here instead?
+    quicksort(arr, pivot_index + 1);
+    quicksort(arr + pivot_index + 1, arr_size - pivot_index - 1);
+  }
 }
 
 int main(void)