9am

Archive for July, 2010|Monthly archive page

The Most Beautiful Code I never wrote

In Algorithms, Programming on July 31, 2010 at 7:45 am

QuickSort can be tricky and atleast one of its implementations printed in a widely used book had in it a subtle bug.

Found an excellent concise implementation in the book “Programming Pearls” by John Bentley.

void quicksort(int left, int right)
{

if ( left <= right ) return;
int pivotIndex = rand(left, right);
int pivotValue  = x[pivotIndex];
swap(x[left], x[pivotIndex]);

int partitionIndex = left;

for (int i = left + 1 ; i <= right; i ++)
if ( x[i] < pivotValue ) swap ( x[++partitionIndex], x[i]);

swap (x[left], x[partitionIndex]);
quicksort(left, partitionIndex -1);
quicksort(partitionIndex + 1, right);

}

Lets see how we could build the above program:

Step 1: Need a find a partition point m. Given m, we need to recurse with quicksort(l, m -1); quicksort (m + 1, u);

Step 2: For recursive programs, an exit strategy is required. if ( l >= u) return;

Step 3: It is difficult to have the pivot value in exactly the middle of the array bcz:

1. We really want to select the pivot location randomly.

2. There is no guarantee that the pivot value will end up dividing the array in two equal subarrays.

As John B mentions in the video, humans are prone to symmetry potentially leading to complex code in the quicksort implementations. So the approach to take is : select a pivot randomly and move it to the first location of the array.

And beautiful code is born !

Advertisements

Wake Up!

In Uncategorized on July 31, 2010 at 7:09 am

It’s time.