qsort: stack based implementationHEADmaster

1 files changed, 50 insertions, 30 deletions

diff --git a/impls/qsort.cpp b/impls/qsort.cpp
index 9f6b1c7..22efbfe 100644
--- a/impls/qsort.cpp
+++ b/impls/qsort.cpp
@@ -4,12 +4,16 @@
  * Commentary: The inplace O(nlog(n)) sortitng algorithm.  Originally designed
  * in C, hence the lack of iostream.
  */
+#include <cstdint>
 #include <cstdio>
 #include <cstdlib>
 #include <fstream>
 #include <iostream>
+#include <stack>
 #include <vector>
 
+using u64 = uint64_t;
+
 #define ARR_SIZE(XS) (sizeof(XS) / sizeof((XS)[0]))
 #define SWAP(A, B) \
   do               \
@@ -19,37 +23,53 @@
     (A) ^= (B);    \
   } while (0)
 
-void print_arr(int *arr, int size)
+void print_arr(u64 *arr, u64 size)
 {
   printf("{\n");
-  for (int i = 0; i < size; ++i)
-    printf("  %d,\n", arr[i]);
+  for (u64 i = 0; i < size; ++i)
+    printf("  %lu,\n", arr[i]);
   printf("}\n");
 }
 
-void quicksort(int *arr, int arr_size)
+struct Partition
+{
+  u64 *arr;
+  u64 arr_size;
+};
+
+void quicksort(u64 *arr, u64 arr_size)
 {
-  // TODO: Use a different sort for small enough sizes?
-  if (arr_size > 1)
+  std::stack<Partition> partitions;
+  partitions.push({arr, arr_size});
+
+  while (!partitions.empty())
   {
-    // TODO: Choose a better pivot maybe?
-    int pivot       = arr[arr_size - 1]; // Choose the last element as pivot
-    int pivot_index = -1;
+    const auto partition = partitions.top();
+    arr                  = partition.arr;
+    arr_size             = partition.arr_size;
+    partitions.pop();
 
-    for (int j = 0; j < arr_size; ++j)
+    // TODO: Use a different sort for small enough sizes?
+    if (arr_size > 1)
     {
-      if (arr[j] < pivot)
+      // TODO: Choose a better pivot maybe?
+      u64 pivot       = arr[arr_size - 1]; // Choose the last element as pivot
+      u64 pivot_index = -1;
+
+      for (u64 j = 0; j < arr_size; ++j)
       {
-        ++pivot_index;
-        std::swap(arr[pivot_index], arr[j]);
+        if (arr[j] < pivot)
+        {
+          ++pivot_index;
+          std::swap(arr[pivot_index], arr[j]);
+        }
       }
-    }
 
-    std::swap(arr[pivot_index + 1], arr[arr_size - 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);
+      partitions.push({arr, pivot_index + 1});
+      partitions.push({arr + pivot_index + 1, arr_size - pivot_index - 1});
+    }
   }
 }
 
@@ -60,21 +80,21 @@ int main(int argc, char *argv[])
 
 #define TEST_SIZE 10
   // randomly generate some numbers
-  int *arr     = new int[TEST_SIZE];
-  int arr_size = TEST_SIZE;
+  // u64 *arr     = new u64[TEST_SIZE];
+  // u64 arr_size = TEST_SIZE;
 
-  for (size_t i = 0; i < TEST_SIZE; ++i)
-    arr[i] = rand() % (2L << 30);
+  // for (size_t i = 0; i < TEST_SIZE; ++i)
+  //   arr[i] = rand() % (2L << 30);
 
   // Use nums.txt
-  // std::ifstream input(argc > 1 ? argv[1] : "nums.txt");
-  // std::vector<int> num_vec;
+  std::ifstream input(argc > 1 ? argv[1] : "nums.txt");
+  std::vector<u64> num_vec;
 
-  // for (std::string line; std::getline(input, line);
-  //      num_vec.push_back(std::stoi(line)))
-  //   continue;
-  // int *arr = &num_vec[0];
-  // int arr_size = num_vec.size();
+  for (std::string line; std::getline(input, line);
+       num_vec.push_back(std::stoi(line)))
+    continue;
+  u64 *arr     = &num_vec[0];
+  u64 arr_size = num_vec.size();
 
   printf("Before: ");
   print_arr(arr, arr_size);
@@ -86,7 +106,7 @@ int main(int argc, char *argv[])
   print_arr(arr, arr_size);
   printf("\n");
 
-  delete[] arr;
+  // delete[] arr;
 
   return 0;
 }