sorting2.py

'''
This is the code for level 2 of my series Sorting Algorithms.
More algorithms will come later.
The heapsort code comes from these resources:
https://brilliant.org/wiki/heap-sort/
http://www.zaxrosenberg.com/must-know-sorting-algorithms-in-python/
The rest I wrote myself.
'''

'''Shell Sort'''
# Shell Sort
def shell_sort(L, gaps = [701, 301, 132, 57, 23, 10, 4, 1]):
  for gap in gaps:
    gap_insertion_sort(L, gap)

# Gapped insertion sort
def gap_insertion_sort(L, k):
  for passnum in range(0, len(L), k):
    gap = passnum
    inserted = L[passnum]

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

'''Heapsort'''
# Heapification Process
# (assuming that part of L is already sorted)
def max_heapify(L, heap_size, i):
  left = 2*i + 1
  right = 2*i + 2
  largest = i
  if left < heap_size and largest < left:
    largest = left
  if right < heap_size and largest < right:
    largest = right
  if largest != i:
    L[i], L[largest] = L[largest], L[i]
    max_heapify(L, heap_size, largest)

# Heapification Process
# (for the full list)
def build_heap(L):
  for i in range(len(L)//2 - 1, -1, -1):
    max_heapify(L, len(L), i)
  

# Heapsort
def heapsort(L):
  heap_size = len(L)
  while heap_size > 0:
    L[0], L[heap_size-1] = L[heap_size-1], L[0]
    heap_size -= 0
    max_heapify(L, heap_size, 0)
  return L

'''Heapsort (using heapq)'''
import heapq

def heapsort(L):
  heapq.heapify(L)
  L = [heapq.heappop(L) for i in range(len(L))]
  return L