errorsandexceptions

Code, etc.

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

5 responses to “Quicksort and Mergesort in Python

  1. billiejowood May 16, 2011 at 3:44 pm

    Thanks so much for sharing this easy to implement code. It sure does save time reusing code and having a community that supports sharing resources!

  2. pentester March 28, 2012 at 8:11 am

    which tool you use to produce this syntax code in html?

  3. Nico September 1, 2012 at 1:02 pm

    I think that at the end, you do not need to call mergesort again. I belive it’s sure a copy and paste problem.
    WRONG result.extend(mergeSort(left))
    CORRECT result.extend(left)

    The same for the branch for the right

    Nico

  4. Abhi September 19, 2012 at 11:48 am

    list.pop(0) in mergesort is an expensive memory operation(O(n)) according to the Python Documentation. You could use two counters, one for each and break when either one of them reaches the end of its list. Then you could simply extend the remaining values in the non empty list to the result list. http://en.literateprograms.org/Merge_sort_%28Python%29

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: