From f7f106195a5caa905e73bef19119f5e59f4d3f2b Mon Sep 17 00:00:00 2001
From: Aryadev Chavali <aryadev@aryadevchavali.com>
Date: Wed, 17 Jul 2024 20:12:07 +0100
Subject: Move qsort.cpp
---
impls/qsort.cpp | 100 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
qsort.cpp | 100 --------------------------------------------------------
2 files changed, 100 insertions(+), 100 deletions(-)
create mode 100644 impls/qsort.cpp
delete mode 100644 qsort.cpp
diff --git a/impls/qsort.cpp b/impls/qsort.cpp
new file mode 100644
index 0000000..d3e8c1d
--- /dev/null
+++ b/impls/qsort.cpp
@@ -0,0 +1,100 @@
+/* qsort.cpp
+ * Date: 2024-06-22
+ * Author: Aryadev Chavali
+ * Commentary: The inplace O(nlog(n)) sortitng algorithm. Originally designed
+ * in C, hence the lack of iostream.
+ */
+#include <cstdio>
+#include <cstdlib>
+
+#define ARR_SIZE(XS) (sizeof(XS) / sizeof((XS)[0]))
+#define SWAP(A, B) \
+ do \
+ { \
+ (A) ^= (B); \
+ (B) ^= (A); \
+ (A) ^= (B); \
+ } while (0)
+
+#define TEST_SIZE 20
+
+void print_arr(int *arr, int size)
+{
+ printf("{");
+ for (int i = 0; i < size - 1; ++i)
+ printf("%d, ", arr[i]);
+ printf("%d}", arr[size - 1]);
+}
+
+void quicksort(int *arr, int arr_size)
+{
+#ifdef TRACE
+ printf("before, arr=");
+ print_arr(arr, arr_size);
+ printf("\n");
+#endif
+ // 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;
+ // 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)
+ {
+ if (arr[i] <= pivot_value)
+ {
+ if (i != pivot)
+ SWAP(arr[i], arr[pivot]);
+ ++pivot;
+ }
+ }
+
+#ifdef TRACE
+ printf("after, arr=");
+ print_arr(arr, arr_size);
+ printf("\n");
+#endif
+ // 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);
+}
+
+int main(void)
+{
+ int arr[TEST_SIZE] = {0};
+ const int size = TEST_SIZE;
+
+ // Generate a completely reverse ordered list
+ /*for (size_t i = 0; i < size; ++i) */
+ /* arr[TEST_SIZE - i - 1] = i;*/
+
+ // Generate a list where the first half is completely sorted and the
+ // other half is in reverse order.
+ for (size_t i = 0; i < size / 2; ++i)
+ arr[i] = i;
+ for (size_t i = size / 2; i < size; ++i)
+ arr[TEST_SIZE - (i - size / 2) - 1] = i;
+
+ printf("Before: ");
+ print_arr(arr, size);
+ printf("\n");
+
+ quicksort(arr, size);
+
+ printf("After: ");
+ print_arr(arr, size);
+ printf("\n");
+
+ return 0;
+}
diff --git a/qsort.cpp b/qsort.cpp
deleted file mode 100644
index d3e8c1d..0000000
--- a/qsort.cpp
+++ /dev/null
@@ -1,100 +0,0 @@
-/* qsort.cpp
- * Date: 2024-06-22
- * Author: Aryadev Chavali
- * Commentary: The inplace O(nlog(n)) sortitng algorithm. Originally designed
- * in C, hence the lack of iostream.
- */
-#include <cstdio>
-#include <cstdlib>
-
-#define ARR_SIZE(XS) (sizeof(XS) / sizeof((XS)[0]))
-#define SWAP(A, B) \
- do \
- { \
- (A) ^= (B); \
- (B) ^= (A); \
- (A) ^= (B); \
- } while (0)
-
-#define TEST_SIZE 20
-
-void print_arr(int *arr, int size)
-{
- printf("{");
- for (int i = 0; i < size - 1; ++i)
- printf("%d, ", arr[i]);
- printf("%d}", arr[size - 1]);
-}
-
-void quicksort(int *arr, int arr_size)
-{
-#ifdef TRACE
- printf("before, arr=");
- print_arr(arr, arr_size);
- printf("\n");
-#endif
- // 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;
- // 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)
- {
- if (arr[i] <= pivot_value)
- {
- if (i != pivot)
- SWAP(arr[i], arr[pivot]);
- ++pivot;
- }
- }
-
-#ifdef TRACE
- printf("after, arr=");
- print_arr(arr, arr_size);
- printf("\n");
-#endif
- // 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);
-}
-
-int main(void)
-{
- int arr[TEST_SIZE] = {0};
- const int size = TEST_SIZE;
-
- // Generate a completely reverse ordered list
- /*for (size_t i = 0; i < size; ++i) */
- /* arr[TEST_SIZE - i - 1] = i;*/
-
- // Generate a list where the first half is completely sorted and the
- // other half is in reverse order.
- for (size_t i = 0; i < size / 2; ++i)
- arr[i] = i;
- for (size_t i = size / 2; i < size; ++i)
- arr[TEST_SIZE - (i - size / 2) - 1] = i;
-
- printf("Before: ");
- print_arr(arr, size);
- printf("\n");
-
- quicksort(arr, size);
-
- printf("After: ");
- print_arr(arr, size);
- printf("\n");
-
- return 0;
-}
--
cgit v1.2.3-13-gbd6f