Skip to content

Instantly share code, notes, and snippets.

@simon-tiger simon-tiger/sorting.py
Last active Apr 27, 2019

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