-
Notifications
You must be signed in to change notification settings - Fork 0
/
quick_sort.c
58 lines (46 loc) · 907 Bytes
/
quick_sort.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
53
54
55
56
57
58
#include<stdio.h>
void disp(int *arr, int size){
printf("\n");
for (int i = 0; i < size; i++){
printf("%d ", arr[i]);
}
printf("\n");
}
void swap(int a, int b, int *arr){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
int partition(int left, int right, int *arr){
int i = left-1;
int j = left;
int pivot = arr[right];
while (j < right){
if (arr[j] < pivot){
i++;
swap(i,j,arr);
}
j++;
}
swap(i+1,right,arr);
return i+1;
}
void quickSort(int left, int right, int *arr){
if (left < right){
int pi = partition(left, right, arr);
quickSort(left, pi-1, arr);
quickSort(pi+1, right, arr);
}
}
int main(){
int size = 0;
scanf("%d", &size);
int arr[size];
for (int i = 0; i < size; i++){
scanf("%d", &arr[i]);
}
disp(arr, size);
quickSort(0, size-1, arr);
disp(arr, size);
return 0;
}