Quicksort

Quicksort.py

from scene import *
import console

def swap(a, i, j):
	tmp = a[i]
	a[i] = a[j]
	a[j] = tmp

def choose_pivot(a):
	return len(a) / 2
 
def partition(a, p, fromIdx, toIdx):
	"Takes an array and a pivot and returns [ < p, p, > p]."
	
	# Move pivot at the first place.
	swap(a, fromIdx, p)
	
	# i points to where the part < p starts and j points to where the array
	# is partitioned
	
	i = fromIdx + 1
	# print a
	for j in range(fromIdx + 1, toIdx + 1):
		# print "a[j] " + str(a[j]) + " a[p] " + str(a[p])
		if a[j] < a[fromIdx]: # Note that the pivot is now at the lowerIdx!
			# print "Swapping " + str(a[i]) + " and " + str(a[j])
			swap(a, i, j)
			i += 1
	
	# Put the pivot in place again.
	swap(a, fromIdx, i - 1)
	

def quicksort(a, fromIdx, toIdx):
	
	if toIdx - fromIdx < 2:
		return
		
	p = choose_pivot(a)
	
	# partition a around p
	partition(a, p, fromIdx, toIdx)
	
	# recursively sort first part
	quicksort(a, fromIdx, p)
	
	# ~                second part
	quicksort(a, p + 1, toIdx)


console.clear()
a = [7, 3, 22, 12, 4, 8, 34, 2]
print a
pIdx = 3
print "Pivot: " + str(a[pIdx])
partition(a, pIdx, 0, len(a) - 1)
print a

First thing I coded on my iPad using Pythonista :)