From f7f106195a5caa905e73bef19119f5e59f4d3f2b Mon Sep 17 00:00:00 2001 From: Aryadev Chavali 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 +#include + +#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 -#include - -#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