QuickSort Variants

QuickSort is a rather well-known sorting algorithm and for many reasons I think it is also fairly deceptive. There are several variants of it and I think each one is interesting in its own right.

Version 1

void quickSort ( int[] a , int lb , int ub ) {

if ( lb >= ub )

    return;

int pIndex = partition ( a , lb , ub );

quickSort ( a , lb , pIndex );

quickSort ( a , pIndex + 1 , ub );

}

int partition ( int[] a , int lb , int ub ) {

int pivot = a [ ( lb + ub ) /2 ];

int left = lb;

int right = ub;

while ( left <= right ) {

          while ( x[left] < pivot ) 

                    left++;

          while ( x[right] > pivot )

                    right--;

          if ( left <= right ) {

                    int t = x[left];

                    x[left] = x[right];

                    x[right] = t;

                    left++;

                    right--;

          }

}

int p = right;

return p;

}

Note: This one does work but note that for some inputs, the split may not be precise. Example: Consider the case where 8,4,1,7,6,2,3,5 is input and 1 is chosen as the pivot first. After 1 pass, 1 would be in its right position, but say 7 is chosen thereafter. Here, in the subsequent pass, 7 will be in its appropriate position but the implementation passed the sublist 7,8 yet again. While this may not incur significant performance penalty, it's worth a note.

Version 2: Canonical QuickSort

int partition ( int[] a , int lb , int ub ) {

int pivot = a[lb]

int i = lb+1;

for ( int j = lb+1; j <= ub; j++ ) {

if ( a[j] < pivot ) {

    swap (a[i], a[j]);

    i++;

}

swap ( a[lb], a[i-1 ); 

}

What I did like about the canonical version was its inherent simplicity. It also makes apparent that each partition has a computational complexity of O(n). As for a counter example for this one, there isn't.

Version 3: Another canonical scheme

int partition ( int[] a , int lb , int ub ) {

int mid = ( lb + ub )/2;
swap ( a[lb] , a[mid] );

int pivot = a[lb];
int left = lb + 1;
int right = ub;

while ( left <= right ) {

while ( a[right] > pivot )
          right--;

while ( left <= right && a[left] <= pivot )
          left++;

if ( left < right ) {
       swap ( a[left] , a[right] );
       left++;
       right--
}

}//end while

swap (a[left],a[right]);
return right;

}

This works fine too. The right returned is correct and it does not work on sub-arrays with pivot already selected previously.