Quicksort

Given a list to be sorted, such as the one below

the main idea in quicksort is to take one guy to be the 'pivot', say the leftmost guy.. (give him a cap)

and then to put bigger guys to his right, and smaller ones to his left, like as follows:

Then, you need to recursively apply the logic, to both the right and the left sublist:

Hence, at the high level, the code is simple, shown below here in Python:

def quickSort(alist, first, last):  
    if first < last:
       splitpoint = partition(alist, first, last)
       quickSort(alist,first,splitpoint-1)
       quickSort(alist,splitpoint+1,last)

where first is the first index, and last the last one. partition performs the positioning, and returns the final position of the pivot.

The tricky part is in doing the partitioning efficiently, without having to create new lists to store the left and right partitions, that is to do it all in-place. The main idea in partition is as follows:

Suppose pivot is the first guy below (red). Initialize a left pointer that starts at the second guy, and a right pointer that starts at the last.



Pythonically,
   pivotvalue = alist[first]

where alist is the name of the list, and first is the first index.

Further

   left = first+1
   right= last

Do as follows:
While the guy pointed to by left is less than pivot, increment left by one (move it one step to the right). Similarly, while the guy pointed to by right is more than pivot, decrement right by one.  Eventually, left and right will be at the positions below:



In code:
   while not done:
       while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1


The outer while loop above continues till right is less than left:

       if rightmark < leftmark:
           done = True

If right is still not less than left, we have to do a swap.  Swap the guys at left and right positions.



Continue the main while loop above, and you get...


Now swap right and pivot:


Partitioning is done - smaller guys to the left of pivot, and bigger ones to the right.

The overall code for partition is as follows:

def partition(alist,first,last):
   pivot = alist[first]

   left = first+1
   right = last

   done = False
   while not done:
       while left <= right and alist[left] <= pivot:
           left = left + 1

       while alist[right] >= pivot and right >= left:
           right = right -1

       if right < left:
           done = True
       else:
           swap(alist, left, right)

   swap(alist, first, right)
   return right