#=======================================================================
# Author: Isai Damier
# Title: QuickSort
# Project: geekviewpoint
# Package: algorithm.sorting
#
# Statement: Given a disordered list of integers (or any other items),
# rearrange the integers in natural order.
#
# Sample Input: [8,5,3,1,9,6,0,7,4,2]
#
# Sample Output: [0,1,2,3,4,5,6,7,8,9]
#
# Time Complexity of Solution:
# Best = Average = O(nlog(n)); Worst = O(n^2).
#
# Approach:
# Quicksort is admirably known as the algorithm that sorts an array
# while preparing to sort it. For contrast, recall that merge sort
# first partitions an array into smaller pieces, then sorts each piece,
# then merge the pieces back. Quicksort actually sorts the array
# during the partition phase.
#
# Quicksort works by selecting an element called a pivot and splitting
# the array around that pivot such that all the elements in, say, the
# left sub-array are less than pivot and all the elements in the right
# sub-array are greater than pivot. The splitting continues until the
# array can no longer be broken into pieces. That's it. Quicksort is
# done.
#
# All this fussing about quicksort sorting while preparing to sort
# may give the impression that it is better than mergesort, but its
# not. In practice their time complexity is about the same -- with
# one funny exception. Because quicksort picks its pivot randomly,
# there is a practically impossible possibility that the algorithm
# may take O(n^2) to compute.
#
# The aforementioned notwithstanding, quicksort is better than
# mergesort if you consider memory usage. Quicksort is an in-place
# algorithm, requiring no additional storage to work.
#=======================================================================
import random
def quicksort( aList ):
_quicksort( aList, 0, len( aList ) - 1 )
def _quicksort( aList, first, last ):
if first < last:
pivot = partition( aList, first, last )
_quicksort( aList, first, pivot - 1 )
_quicksort( aList, pivot + 1, last )
def partition( aList, first, last ) :
pivot = first + random.randrange( last - first + 1 )
swap( aList, pivot, last )
for i in range( first, last ):
if aList[i] <= aList[last]:
swap( aList, i, first )
first += 1
swap( aList, first, last )
return first
def swap( A, x, y ):
A[x],A[y]=A[y],A[x]
import unittest
from algorithms import sorting
def testQuicksort( self ):
A = [8, 5, 3, 1, 9, 6, 0, 7, 4, 2, 5]
sorting.quicksort( A )
for i in range( 1, len( A ) ):
if A[i - 1] > A[i]:
self.fail( "quicksort method fails." )
