#include <stdio.h>
#include <stdlib.h>
#define LEN 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
void sort(int*, int, int(*)(int, int));
void quickSort(int*, int, int, int(*)(int, int));
void print(int*, int len);
int ascending(int, int);
int descending(int, int);
int main(void) {
int number[LEN] = {10, 9, 1, 2, 5, 3, 8, 7, 12, 11};
sort(number, LEN, ascending);
print(number, LEN);
sort(number, LEN, descending);
print(number, LEN);
return 0;
}
void sort(int* number, int len, int(*comp)(int, int)) {
quickSort(number, 0, len - 1, comp);
}
void quickSort(int* number, int left, int right, int(*comp)(int, int)) {
if(left < right) {
int axis = partition(number, left, right, comp);
quickSort(number, left, axis - 1, comp);
quickSort(number, axis + 1, right, comp);
}
}
int partition(int* number, int left, int right, int(*comp)(int, int)) {
int s = number[left];
int axis = partitionUnprocessed(number, left + 1, right, s, comp);
SWAP(number[left], number[axis]);
return axis;
}
int partitionUnprocessed(int* number, int left, int right,
int s, int(*comp)(int, int)) {
int i = lookRight(number, left, right, s, comp);
int j = lookLeft(number, right, i, s, comp);
if(i < j) {
SWAP(number[i], number[j]);
return partitionUnprocessed(number, i + 1, j - 1, s, comp);
}
return j;
}
int lookRight(int* number, int from, int to, int s, int(*comp)(int, int)) {
int i = from;
while(i < to + 1 && comp(number[i], s) <= 0) { i++; }
return i;
}
int lookLeft(int* number, int from, int to, int s, int(*comp)(int, int)) {
int j = from;
while(j > to - 1 && comp(number[j], s) > 0) { j--; }
return j;
}
void print(int* arr, int len) {
int i;
for(i = 0; i < len; i++) { printf("%d ", arr[i]); }
printf("\n");
}
int ascending(int a, int b) { return a - b; }
int descending(int a, int b) { return -ascending(a, b); }
|
沒有留言:
張貼留言