Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Sorting Algorithms studies
import sys
import time
#Deal with Python2 and Python3 inputs
def getInput(prompt):
if (sys.version[0] == "2"):
return raw_input(prompt)
else:
return input(prompt)
testInput = getInput("Input an array: ")
if type(testInput == str):
testInput = [int(i) for i in testInput.strip("[]").split(",")]
# Insertion sort
def insertion(inputArray):
for index, item in enumerate(inputArray):
#start at 0 index
if (index > 0):
moveIndex = index-1
while(item < inputArray[moveIndex] and moveIndex >= 0):
temp = inputArray[moveIndex]
inputArray[moveIndex] = item
inputArray[moveIndex + 1] = temp
moveIndex -= 1
return inputArray
#testInputCopy = testInput
#print( insertion(testInputCopy) )
# Merge sort
# based off algorithm from here: http://geeksquiz.com/merge-sort/
def merge(inputArray, start, divide, end):
j = 0 #index to follow in non-focused list
k = start
left = inputArray[start:divide]
right = inputArray[divide:end]
for index, item in enumerate(left):
while j < len(right):
if item > right[j]:
inputArray[k] = right[j]
j += 1
k += 1
else:
break
inputArray[k] = item
k += 1
def mergeSort(inputArray, start, end):
if start < end - 1:
submax = int((start + end)/2)
mergeSort(inputArray, start, submax)
mergeSort(inputArray, submax, end)
merge(inputArray, start, submax, end)
else:
return inputArray
returnCopy = testInput
print("before:")
print(returnCopy)
mergeSort(returnCopy, 0, len(testInput))
print("after:")
print( returnCopy )
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.