-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathquick.c
More file actions
72 lines (64 loc) · 1.86 KB
/
quick.c
File metadata and controls
72 lines (64 loc) · 1.86 KB
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
/*
* =========================================================
* Filename: quick.c
* Description: The key process in quickSort is partition()
*
* =========================================================
*/
#include <stdio.h>
#define SWAP(a,b) do{int temp;temp=a;a=b;b=temp;}while(0)
int partition(int arr[],int l,int r);
void quickSort(int arr[],int l,int r);
void printArray(int arr[],int n);
// Driver program to test above functions
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
/*---------------------------------------------------
This function takes first element as pivot,
places the pivot element at its
correct position in sorted array,
and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right of pivot
[l , i-1] < pivot
i -> pivot
[i+1 , r] >= pivot
link : https://gist.github.com/tinylamb/7624054
以[0,n-1]为例解释各个参数的含义
[1,l]<p l指向最后一个小于p的数
(r,n]>p r+1指向第一个大于p的数
(l,i)=p
[i,r] 未处理的数
*---------------------------------------------------*/
int partition(int arr[],int l,int r){
int pivot = arr[l];
int i = l;//be sure [start+1 , i] < pivot
for(int j = l+1;j <= r;j++){
if(arr[j] < pivot){
i++;
SWAP(arr[i],arr[j]);
}
}
SWAP(arr[l],arr[i]);//make [start,i-1] < pivot
return i; // i point to the right place of pivot
}
void quickSort(int arr[],int l,int r){
if(l < r){
int p = partition(arr,l,r);
quickSort(arr,l,p-1);
quickSort(arr,p+1,r);
}
}
void printArray(int arr[],int n){
int i = 0;
while(i < n){
printf("%d%s",arr[i],(i == n-1)?"\n":" ");
i++;
}
}