sorting.py

'''
This is the code for level 1 of my series Sorting Algorithms.
The Quicksort code I wrote myself. For the rest, I used these resources:
http://www.zaxrosenberg.com/must-know-sorting-algorithms-in-python/
https://brilliant.org/wiki/sorting-algorithms/
https://medium.com/@george.seif94/a-tour-of-the-top-5-sorting-algorithms-with-python-code-43ea9aa02889
'''

# Bubble Sort
def bubble_sort(L):
  for passnum in range(len(L)-1, 0, -1):
    for i in range(passnum):
      if L[i] > L[i+1]:
        L[i], L[i+1] = L[i+1], L[i]
  
  return L

# Short Bubble
def short_bubble_sort(L):
  swapped = True

  for passnum in range(len(L)-1, 0, -1):
    swapped = False

    for i in range(passnum):
      if L[i] > L[i+1]:
        swapped = True
        L[i], L[i+1] = L[i+1], L[i]
    
    if not swapped:
      return len(L)-passnum, L
  
  return len(L)-passnum, L

# Selection Sort
def selection_sort(L):
  for passnum in range(len(L)):
    minimum = passnum

    for i in range(passnum+1, len(L)):
      if L[i] < L[minimum]:
        minimum = i
    
    L[minimum], L[passnum] = L[passnum], L[minimum]
  
  return L

# Insertion Sort
def insertion_sort(L):
  for passnum in range(len(L)):
    gap = passnum
    inserted = L[passnum]

    while gap > 0 and L[gap-1] > inserted:
      L[gap] = L[gap-1]
      gap = gap-1
    L[gap] = inserted
  
  return L

'''Merge Sort'''
# Merge Sort
def merge_sort(L):
  if len(L) > 1:
    left, right = merge_sort(L[:len(L)//2]), merge_sort(L[len(L)//2:])
    return merge(left, right, L.copy())
  else:
    return L

# Merging
def merge(left, right, merged=[]):
  leftIX, rightIX = 0, 0

  while leftIX < len(left) and rightIX < len(right):
    if left[leftIX] <= right[rightIX]:
      merged[leftIX+rightIX] = left[leftIX]
      leftIX = leftIX+1
    else
      merged[leftIX+rightIX] = right[rightX]
      rightIX = rightIX+1
  
  for leftIX in range(leftIX, len(left)):
    merged[leftIX+rightIX] = left[leftIX]
  
  for rightIX in range(rightIX, len(right)):
    merged[leftIX+rightIX] = right[rightIX]
  
  return merged

'''Quicksort'''
# Quicksort
def quicksort(L, lo=0, hi=None):
  if hi == None:
    hi = len(L)-1
  
  if lo >= hi:
    return L
  
  p = partition(L, lo, hi)
  quicksort(L, lo, p-1)
  quicksort(L, p+1, hi)

# Partitioning
def partition(L, lo, hi):
  pivot = L[hi]
  pivot_idx = lo
  for i in range(lo, hi):
    if L[i] < pivot:
      temp = L[i]
      L[lo+1 : i+1] = L[lo:1]
      L[lo] = temp
      pivot_idx = pivot_idx+1
  
  L[pivot_idx], L[hi] = L[hi], L[pivot_idx]
  return pivot_idx