Skip to content

Instantly share code, notes, and snippets.

@vhalli
Created March 3, 2013 15:51
Show Gist options
  • Save vhalli/95eed1ed9efa9e94925e to your computer and use it in GitHub Desktop.
Save vhalli/95eed1ed9efa9e94925e to your computer and use it in GitHub Desktop.
Visualizing quicksort in python
from pylab import *
from random import shuffle
def qsort(l, s, e):
if s < e:
mid = part(l, s, e)
qsort(l, s, mid-1)
qsort(l, mid+1, e)
else:
return
def part(l, s, e):
pivot = l[e]
end = s-1
start = e
sorted = 0
while not sorted:
while not sorted:
end = end+1
if end == start:
sorted = 1
break
if l[end] > pivot:
l[start] = l[end]
line.set_ydata(u)
draw()
break
while not sorted:
start = start-1
if start == end:
sorted = 1
break
if l[start] < pivot:
l[end] = l[start]
line.set_ydata(u)
draw()
break
l[start] = pivot
line.set_ydata(u)
draw()
return start
if __name__ == "__main__":
ion()
u = range(300)
shuffle(u)
line, = plot(range(300), u, 'r.')
qsort(u, 0, len(u)-1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment