Created
January 29, 2013 02:11
-
-
Save dannyroa/4661097 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment