|
| 1 | +#include <stdio.h> |
| 2 | +#include <stdlib.h> |
| 3 | +#include <time.h> |
| 4 | +/* Author: Jonathan Lebron 2013 |
| 5 | + * Quick Sort (in-place): |
| 6 | + * 1. Shuffle the array |
| 7 | + * 2. Partition |
| 8 | + * 3. Sort each piece recursively |
| 9 | + */ |
| 10 | + |
| 11 | +// forward declarations |
| 12 | +void shuffle(int a[], int size); |
| 13 | +void sort(int a[], int lo, int hi); |
| 14 | +int partition(int a[], int lo, int hi); |
| 15 | + |
| 16 | +void quickSort(int a[], int size) |
| 17 | +{ |
| 18 | + shuffle(a, size); // probabilistic guarantee against worst case |
| 19 | + sort(a, 0, size-1); |
| 20 | +} |
| 21 | + |
| 22 | +// Knuth shuffle (http://en.wikipedia.org/wiki/Knuth_shuffle) |
| 23 | +void shuffle(int a[], int size) |
| 24 | +{ |
| 25 | + int r; |
| 26 | + int temp; |
| 27 | + for (int i = 0; i < size; i++) { |
| 28 | + srand(time(NULL)); |
| 29 | + r = rand() % (i+1); |
| 30 | + temp = a[i]; |
| 31 | + a[i] = a[r]; |
| 32 | + a[r] = temp; |
| 33 | + } |
| 34 | +} |
| 35 | + |
| 36 | +void sort(int a[], int lo, int hi) |
| 37 | +{ |
| 38 | + if (hi <= lo) return; |
| 39 | + int j = partition(a, lo, hi); |
| 40 | + sort(a, lo, j-1); |
| 41 | + sort(a, j+1, hi); |
| 42 | +} |
| 43 | + |
| 44 | +int partition(int a[], int lo, int hi) |
| 45 | +{ |
| 46 | + int i = lo, j = hi+1, temp; |
| 47 | + while(1){ |
| 48 | + // find item on left to swap |
| 49 | + while (a[++i] < a[lo]){ |
| 50 | + if (i == hi) break; |
| 51 | + }; |
| 52 | + |
| 53 | + // find item on right to swap |
| 54 | + while (a[lo] < a[--j]){ |
| 55 | + if (j == lo) break; |
| 56 | + } |
| 57 | + |
| 58 | + // if pointers have crossed, we are done partitioning |
| 59 | + if (i >= j) break; |
| 60 | + |
| 61 | + temp = a[i]; |
| 62 | + a[i] = a[j]; |
| 63 | + a[j] = temp; |
| 64 | + } |
| 65 | + |
| 66 | + // swap pivot element with j, return index j |
| 67 | + temp = a[lo]; |
| 68 | + a[lo] = a[j]; |
| 69 | + a[j] = temp; |
| 70 | + return j; |
| 71 | +} |
| 72 | + |
| 73 | +int main(int argc, char *argv[]) |
| 74 | +{ |
| 75 | + if (argc < 2) { |
| 76 | + printf("ERROR: Must provide at least one argument!\n"); |
| 77 | + exit(1); |
| 78 | + } |
| 79 | + |
| 80 | + int a[argc-1]; |
| 81 | + for (int i = 1; i < argc; i++){ |
| 82 | + a[i-1] = atoi(argv[i]); |
| 83 | + } |
| 84 | + |
| 85 | + quickSort(a, argc-1); |
| 86 | + |
| 87 | + printf("Done sorting... Result is {"); |
| 88 | + for (int i = 0; i < argc-1; i++){ |
| 89 | + printf("%d, ", a[i]); |
| 90 | + } |
| 91 | + printf("\b\b}\n"); |
| 92 | +} |
| 93 | + |
0 commit comments