1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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;
}
|
