The electric word.
You've stumbled across my blog: the home of my most private, innermost thoughts and reflections. And random cat videos.
$ python challenge: in-place quicksort01/06/2012

Continuing with the Python challenge, the next step was to implement the in-place version of quicksort. Slightly more complex than the simple quicksort, this version uses less space by sorting the list in place. It keeps the same time complexity (O(n log n) average case)

# swaps the two elements in the passed list def swap(list, index1, index2): index1Val = list[index1] index2Val = list[index2] list[index1] = index2Val list[index2] = index1Val # partitions and sorts the list at the specified points def partition(list, left, right, pivotIndex): pivotVal = list[pivotIndex] swap(list, pivotIndex, right) storeIndex = left for index in range(left, right): if list[index] < pivotVal: swap(list, index, storeIndex) storeIndex = storeIndex + 1 swap(list, storeIndex, right) return storeIndex # sort the list def quicksort(list, left, right): if left < right: # get a pivot index pivotIndex = Random.getRandomInt(len(listToSort)) while pivotIndex < left or pivotIndex > right: pivotIndex = Random.getRandomInt(len(listToSort)) pivotNewIndex = partition(list, left, right, pivotIndex) # Recursively sort elements on each side quicksort(list, left, pivotNewIndex - 1) quicksort(list, pivotNewIndex + 1, right)