-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.c
52 lines (44 loc) · 1.21 KB
/
main.c
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
#include <stdio.h>
#include <stdlib.h>
#define SWAP(x, y) do {int temp = x;x = y;y = temp;} while (0)
#define ARR_SIZE 10
#define MAX_VAL 100
#define RAND_SEED 773
int partition(int arr[], int lo, int hi) {
int pivot = arr[(lo + hi) / 2];
int i = lo - 1;
int j = hi + 1;
while (1) {
do {i++;} while (arr[i] < pivot);
do {j--;} while (arr[j] > pivot);
if (i >= j) {return j;}
SWAP(arr[i], arr[j]);
}
}
void quick_sort(int *arr, int lo, int hi) {
if (lo >= 0 && hi >= 0 && lo < hi) {
int p = partition(arr, lo, hi);
quick_sort(arr, lo, p); // Pivot included in left half
quick_sort(arr, p + 1, hi);
}
}
int main() {
srand(RAND_SEED); // Using srand and seeding with constant to get reproducible results
int arr[ARR_SIZE];
for (int i = 0; i < ARR_SIZE; i++) {
arr[i] = rand() % MAX_VAL;
}
printf("Unsorted array: ");
for (int i = 0; i < ARR_SIZE; i++) {
printf("%.2d ", arr[i]);
}
printf("\n");
// algo! start
quick_sort(arr, 0, ARR_SIZE - 1);
// algo! end
printf("Sorted array: ");
for (int i = 0; i < ARR_SIZE; i++) {
printf("%.2d ", arr[i]);
}
printf("\n");
}