Skip to content

Instantly share code, notes, and snippets.

@avenet
Last active March 2, 2016 15:02
Show Gist options
  • Save avenet/399adbc846cccc56cfb2 to your computer and use it in GitHub Desktop.
Save avenet/399adbc846cccc56cfb2 to your computer and use it in GitHub Desktop.
Implementing quicksort in place
def swap(array, i, j):
temp = array[i]
array[i] = array[j]
array[j] = temp
def partition(array, i, j):
pos = i
pivot = array[j]
for k in xrange(i, j):
if array[k] < pivot:
swap(array, k, pos)
pos += 1
swap(array, j, pos)
return pos
def do_quicksort(array, i, j):
if i >= j:
return
print i,j
pivot = partition(array, i, j)
do_quicksort(array, i, pivot-1)
do_quicksort(array, pivot+1, j)
def quicksort(items):
do_quicksort(items, 0, len(items)-1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment