void swap(int *A, int *B) {
int tmp = *A;
*A = *B;
*B = tmp;
}
void print(int *arr, int n) {
int i = 0;
for (;i < n;i++)
printf("%d ", arr[i]);
puts("");
}
/* first: we should get the larger number from
* the two numbers which are the first differnt
* from each other, when we scan the arr array
* from left to right */
/* error: return -1
* other: return the index of array
* */
void findpivot(int left, int right, int *arr, int *ret) {
int pos = left;
int first = arr[left++];
*ret = -1;
while(left <= right) {
if (first < arr[left]) {
*ret = left;
return ;
} else if (first > arr[left]) {
*ret = pos;
return ;
}
left++;
}
}
/* return the left bound of right array of partition */
void partition(int left, int right, int *arr, int key, int *ret_pos) {
int l = left;
int r = right;
do {
swap(&arr[l], &arr[r]);
while (arr[l] < key)
l++;
while (arr[r] >= key)
r--;
} while(l != r+1);
*ret_pos = l;
}
void q_sort(int left, int right, int *array) {
int pos;
int lright;
findpivot(left, right, array, &pos);
if (pos < 0) return ;
partition(left, right, array, array[pos], &lright);
q_sort(left, lright-1, array);
q_sort(lright, right, array);
}
void quick_sort(int *arr, int n) {
q_sort(0, n-1, arr);
}
|
