#include <iostream> using namespace std;
int partition(int arr[], int l, int r) { int i = l - 1; int j = r; int v = arr[r]; int tmp;
for (; ;) { while (arr[++i] < v) ; while (v < arr[--j]) if (j == l) break; if (i >= j) break; tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } tmp = arr[i]; arr[i] = arr[r]; arr[r] = tmp; return i; }
void quicksort(int arr[], int l, int r) { int i; if (r <= l) return; i = partition(arr, l, r); quicksort(arr, l, i-1); quicksort(arr, i+1, r); }
void select(int arr[], int l, int r, int k) { int i; if (r <= l) return; i = partition(arr, l, r); if (i > k) select(arr, l, i-1, k); else if (i < k) select(arr, i+1, r, k); else printf("%d th number is %d\n", k, arr[k]); }
int main() { int arr[15] = {10, 21, 2, 1, 3, 45, 2, 932, 32, 27, 86, 65, 576, 434, 76753}; int arr2[15] = {10, 21, 2, 1, 3, 45, 2, 932, 32, 27, 86, 65, 576, 434, 76753}; int i; cout << "Original array" << endl; for (i = 0; i < 15; i++) cout << arr[i] << " "; cout << endl << endl;
quicksort(arr, 0, 14);
cout << "Sorted array" << endl; for (i = 0; i < 15; i++) cout << arr[i] << " "; cout << endl;
select(arr2, 0, 14, 13); return 0; }
|