// Traces the basic partitioning technique in Sedgewick #include #include 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 i,int j) { int k; for (k=0;k= pivot. int i = ell-1, j = r; Item v = a[r]; for (;;) { // Since pivot is the right end, this while has a sentinel. // Stops at any element >= pivot while (1) { ++i; dump(a,i,j); if (!less(a[i], v)) break; printf(" Left continues\n"); } printf(" Left positioned\n"); // Stops at any element <= pivot (but not the pivot) or at the left end while (1) { --j; dump(a,i,j); if (!less(v,a[j])) break; if (j == ell) break; printf(" Right continues\n"); } if (i >= j) break; // Don't need to swap printf(" Right positioned\n"); exch(a[i], a[j]); dump(a,i,j); printf(" After swap\n"); } printf(" Pointers collided\n"); exch(a[i], a[r]); // Place pivot at final position for sort return i; } int main() { int i,j; scanf("%d",&arrSize); arr=(int*) malloc(arrSize*sizeof(int)); if (!arr) { printf("malloc failed %d\n",__LINE__); exit(0); } for (i=0;i",arr[j]); else printf(" %2d ",arr[j]); printf(" Pivot positioned\n"); }