Quicksort In Pythonby Isai Damier, Android Engineer @ Google

```#=======================================================================
#  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." )
```