Wednesday, May 16, 2012

Quicksort() using python

One method of sorting lists is to use the quicksort.  The elements in the list must have a strict weak order and the index of the array can be of any discrete type.


Follow these steps to implement:
  1. Choose any element of the list to be the pivot.
  2. Divide all other elements (except the pivot) into two partitions.
    • All elements less than the pivot must be in the first partition (lower half list).
    • All elements greater than the pivot must be in the second partition (upper half list).
  3. Use recursion to sort both partitions.
  4. Join the first sorted partition, the pivot, and the second sorted partition
The run time of quicksort ranges from O(n log n) with the best pivots, to O(n2) with the worst pivots, where n is the number of elements in the list.  (O is complexity)



def qsort(list):
    if not list:
        return []
    else:
        pivot = list[0]
        less = [x for x in list     if x <  pivot]
        more = [x for x in list[1:] if x >= pivot]
        return qsort(less) + [pivot] + qsort(more)

Example:
someList = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3]
print qsort( someList )
[1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9, 9, 9]


Enjoy the sort.

1 comment:

Unknown said...

What's the point of this? An exercise in learning basic algorithms? The sort algorithms built in to Python are implemented in C and benchmark significantly faster, rewriting them gives you no practical benefit.

The Python source contains a very interesting discussion about practical sort implementations, remember that Quicksort assumes perfectly uniform memory lookup when in practice random seeks are much slower than reading memory in sequence; it also assumes a totally shuffled array when it may be in the average lists are only partially unordered, in which case a more appropriate solution with a lower average-case Big-O may exist (at the expense of worst case, of course).