"""
Learning Goals:
- Analyze and improve the efficiency of different programs
-- Recognize and trace common sorting algorithms
-- Understand why different sorting algoritms have different runtimes
"""
def selectionSort(L):
# Go through each index to move an element into
for i in range(len(L)-1):
# Find the smallest element
minIndex = i
for j in range(i+1, len(L)):
if L[j] < L[minIndex]:
minIndex = j
# Swap the two elements
tmp = L[minIndex]
L[minIndex] = L[i]
L[i] = tmp
def insertionSort(L):
# Go through each element that needs to be inserted
for i in range(1, len(L)):
tmp = L[i]
j = i-1
# Move elements forward while they're bigger
while j >= 0 and L[j] > tmp:
L[j+1] = L[j]
j = j - 1
# Move the original element into its new spot
L[j+1] = tmp
def mergeSort(L):
# Base case: empty and one-element lists are already sorted
if len(L) == 0 or len(L) == 1:
return
# Split the list in half, recursively sort each half
mid = len(L) // 2
left = L[:mid]
right = L[mid:]
mergeSort(left)
mergeSort(right)
# Merge the two sorted lists back together
leftIndex = 0
rightIndex = 0
i = 0
# Only need to compare the first unsorted elements,
# because it's sorted!
while leftIndex < len(left) and rightIndex < len(right):
if left[leftIndex] < right[rightIndex]:
L[i] = left[leftIndex]
leftIndex = leftIndex + 1
else:
L[i] = right[rightIndex]
rightIndex = rightIndex + 1
i = i + 1
# Add any remaining elements to the end of the list
while leftIndex < len(left):
L[i] = left[leftIndex]
leftIndex = leftIndex + 1
i = i + 1
while rightIndex < len(right):
L[i] = right[rightIndex]
rightIndex = rightIndex + 1
i = i + 1
lst = [ 8, 4, 2, 5, 1, 3, 7, 9]
# selectionSort(lst)
# insertionSort(lst)
# mergeSort(lst)
print(lst)