Skip to content

Instantly share code, notes, and snippets.

@simon-tiger simon-tiger/sorting2.py
Last active Apr 26, 2019

Embed
What would you like to do?
'''
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
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.