aboutsummaryrefslogtreecommitdiff
path: root/qsort.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'qsort.cpp')
-rw-r--r--qsort.cpp100
1 files changed, 0 insertions, 100 deletions
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;
-}