quicksort.py

#coding: utf-8
# Quicksort in Python

from random import randint

def sort(array):
	def partition(array, left, right):
		global swaps
		# Improving worst case (at the cost of making average case suffer a little!)
		#~ p = (left + right) // 2
		#~ array[p], array[right] = array[right], array[p]
		#~ swaps += 1
		
		pivot = array[right]
		i = left - 1
		for j in range(left, right):
			if array[j] <= pivot:
				i += 1
				array[i], array[j] = array[j], array[i]
				swaps += 1
		i += 1
		array[i], array[right] = array[right], array[i]
		swaps += 1
		return i

	def sort(array, left, right):
		if left < right:
			pivot_index = partition(array, left, right)
			sort(array, left, pivot_index - 1)
			sort(array, pivot_index + 1, right)
			
	sort(array, 0, len(array) - 1)


def run_test(array):
	global swaps
	swaps = 0
	sort(array)
	print(array)
	print(swaps)
	print()

def test_average(array):
	print("average")
	run_test(array[:])

def test_ordered(array):
	print("ordered")
	a = array[:]
	a.sort()
	run_test(a)
	
def test_reversed(array):
	print("reversed")
	a = array[:]
	a.sort()
	a.reverse()
	run_test(a)
	
def create_array(size):
	array = []
	used = set()
	for i in range(size):
		value = randint(5, size + 5)
		if value not in used:
			array.append(value)
			used.add(value)
	return array


VALUES = [3, 7, 8, 5, 2, 1, 9, 5, 4]
swaps = 0
array = create_array(50)
print(array)
print()
test_average(array)
test_ordered(array)
test_reversed(array)