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
101
102
103
104
105
106
107
108
109
110
111
112
|
/* 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 <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 \
{ \
(A) ^= (B); \
(B) ^= (A); \
(A) ^= (B); \
} while (0)
void print_arr(u64 *arr, u64 size)
{
printf("{\n");
for (u64 i = 0; i < size; ++i)
printf(" %lu,\n", arr[i]);
printf("}\n");
}
struct Partition
{
u64 *arr;
u64 arr_size;
};
void quicksort(u64 *arr, u64 arr_size)
{
std::stack<Partition> partitions;
partitions.push({arr, arr_size});
while (!partitions.empty())
{
const auto partition = partitions.top();
arr = partition.arr;
arr_size = partition.arr_size;
partitions.pop();
// TODO: Use a different sort for small enough sizes?
if (arr_size > 1)
{
// 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)
{
if (arr[j] < pivot)
{
++pivot_index;
std::swap(arr[pivot_index], arr[j]);
}
}
std::swap(arr[pivot_index + 1], arr[arr_size - 1]);
partitions.push({arr, pivot_index + 1});
partitions.push({arr + pivot_index + 1, arr_size - pivot_index - 1});
}
}
}
int main(int argc, char *argv[])
{
(void)argc;
(void)argv;
#define TEST_SIZE 10
// randomly generate some numbers
// 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);
// Use nums.txt
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;
u64 *arr = &num_vec[0];
u64 arr_size = num_vec.size();
printf("Before: ");
print_arr(arr, arr_size);
printf("\n");
quicksort(arr, arr_size);
printf("After: ");
print_arr(arr, arr_size);
printf("\n");
// delete[] arr;
return 0;
}
|
