-
Notifications
You must be signed in to change notification settings - Fork 11
/
quick_sort.c
71 lines (60 loc) · 1.63 KB
/
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
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
#include <stdlib.h>
void swap(int* a, int* b){
int temp = *a;
*a = *b;
*b = temp;
}
int partition (int arr[], int left_index, int right_index){
int pivot = arr[right_index];
int pivot_index = right_index;
right_index--; /*pivot exists at the right index*/
while(left_index <= right_index){
if(arr[left_index] < pivot){
left_index++;
continue;
}
else if(arr[right_index] > pivot){
right_index--;
continue;
}
else{
swap(&arr[left_index], &arr[right_index]);
}
}
/*Now the left index point to location where pivot must go*/
swap(&arr[left_index], &arr[pivot_index]);
return left_index;
}
void quick_sort_func(int arr[], int left_index, int right_index)
{
if (left_index < right_index) {
int partition_index = partition(arr, left_index, right_index);
/*recursively sort first and second halves*/
quick_sort_func(arr, left_index, partition_index - 1);
quick_sort_func(arr, partition_index + 1, right_index);
}
}
void print_array_func(int arr[], int size){
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[6][8] = { {2, 31, 13, 15, 61, 7, 43, 44},
{102, 110, 3, -4, 6, 7, -23, 512},
{12, -11, 103, 54, 16, 37, 23, 55},
{1, 11, 13, -5, 6, -7, -23, 43},
{129, -11, -13, 5, -6, 7, 32, 66},
{-129, -11, -13, -5, -6, -7, -32, -66} };
for(int i=0; i<6; i++){
int arr_size = sizeof(arr[i]) / sizeof(arr[i][0]);
printf("\nGiven array is \n");
print_array_func(arr[i], arr_size);
quick_sort_func(arr[i], 0, arr_size - 1);
printf("Sorted array is\n");
print_array_func(arr[i], arr_size);
}
return 0;
}