errorsandexceptions

Code, etc.

Tag Archives: sorting

Quicksort and Mergesort in Python

I wrote these small implementations of the quicksort and mergesort algorithms in Python. They take a list of numbers and return it sorted from lowest to highest. The WordPress code tags behave very strangely.

Here is Quicksort:

# Sorting a List using Quicksort in Python
# 2011-05-16

def quickSort(toSort):
	if len(toSort) <= 1:
		return toSort

	end = len(toSort) - 1
	pivot = toSort[end]

	low = []
	high = []

	for num in toSort[:end]:
		if num <= pivot:
			low.append(num)
		else:
			high.append(num)

	sortedList = quickSort(low)
	sortedList.append(pivot)
	sortedList.extend(quickSort(high))

	return sortedList

def main():
	l = [1, 6, 7, 2, 76, 45, 23, 4, 8, 12, 11]
	sortedList = quickSort(l)
	print sortedList

if __name__ == '__main__':
	main()

And Mergesort:

# Sorting a List using Mergesort in Python
# 2011-05-16

def mergeSort(toSort):
	if len(toSort) <= 1:
		return toSort

	mIndex = len(toSort) / 2
	left = mergeSort(toSort[:mIndex])
	right = mergeSort(toSort[mIndex:])

	result = []
	while len(left) > 0 and len(right) > 0:
		if left[0] > right[0]:	
			result.append(right.pop(0))
		else:
			result.append(left.pop(0))

	if len(left) > 0:
		result.extend(mergeSort(left))
	else:
		result.extend(mergeSort(right))

	return result

def main():
	l = [1, 6, 7, 2, 76, 45, 23, 4, 8, 12, 11]
	sortedList = mergeSort(l)
	print sortedList

if __name__ == '__main__':
	main()
Advertisements