// Ordinary recursive quicksort with different partitioning implementations // See Sedgewick for details #include #include #include #define generateRandom(minRange,maxRange) \ (minRange)+abs(random()) % ((maxRange)-(minRange)+1) typedef int Item; #define key(A) (A) #define less(A, B) (key(A) < key(B)) #define exch(A, B) { Item t = A; A = B; B = t; } #define compexch(A, B) if (less(B, A)) exch(A, B) Item *arr; int arrSize; void dump(Item *a,int low,int high) { int i; if (low<=high) { printf(" i key\n"); for (i=low;i<=high;i++) printf("%2d %7d\n",i,arr[i]); } } int partitionBothRight(Item *a,int p,int r) // From CLRS, 2nd ed. // Conceptually the simplest partitioner // Subscripts <= i store elements <= pivot (arr[r]) // Subscripts in range i+1 .. j store elements > pivot { int i,j; Item x,temp; printf("Input\n"); dump(arr,p,r); x=arr[r]; i=p-1; for (j=p;j= pivot. int i = ell-1, j = r; Item v = a[r]; printf("Input\n"); dump(arr,ell,r); for (;;) { // Since pivot is the right end, this while has a sentinel. // Stops at any element >= pivot while (less(a[++i], v)) ; // Stops at any element <= pivot (but not the pivot) or at the left end while (less(v, a[--j])) if (j == ell) break; if (i >= j) break; // Don't need to swap exch(a[i], a[j]); } exch(a[i], a[r]); // Place pivot at final position for sort printf("Left output\n"); dump(arr,ell,i-1); printf("In final position\n"); printf("%2d %7d\n",i,arr[i]); printf("Right output\n"); dump(arr,i+1,r); return i; } void quicksort(Item *a, int ell, int r) { if (r <= ell) return; int i = partition(a, ell, r); quicksort(a, ell, i-1); quicksort(a, i+1, r); } int partitionFast(Item *a, int ell, int r) { // Similar to partition, but a little faster. See problem 7.3. // The returned value is NOT the final position for the pivot! int i = ell-1, j = r+1; Item v = a[r]; printf("Input\n"); dump(arr,ell,r); for (;;) { while (less(a[++i], v)) ; // Note that j is initialized so this while stops at the pivot // the first iteration of the enclosing for. while (less(v, a[--j])) ; if (i < j) exch(a[i], a[j]) else { printf("Left output\n"); dump(arr,ell,i-1); printf("Right output\n"); dump(arr,i,r); return i; } } } void quicksortFast(Item *a, int ell, int r) { if (r <= ell) return; int i = partitionFast(a, ell, r); quicksortFast(a, ell, i-1); quicksortFast(a, i, r); } int main() { int i,seed; scanf("%d",&arrSize); arr=(int*) malloc(arrSize*sizeof(int)); if (!arr) { printf("malloc failed %d\n",__LINE__); exit(0); } scanf("%d",&seed); printf("quicksort with both pointers going right\n"); srandom(seed); for (i=0;i