Previously asked here.
I would like to get my code for implementation of simple sorting algorithms in idiomatic python code reviewed. I am looking for feedback on python idioms used, better ways of doing the same thing. I am familiar with FP, and I am willing to put in effort to get myself familiar with pythonic idioms such as list comprehensions and enumerators. Hence I would also like feedback on if any of the explicit loops can be converted to these.
import doctest
from hypothesis import given
import hypothesis.strategies as st
Insertion Sort
def insertionsort(items):
"""
>>> insertionsort([])
[]
>>> insertionsort([1])
[1]
>>> insertionsort([1,2,3,4,5])
[1, 2, 3, 4, 5]
>>> insertionsort([4,5,3,1,2])
[1, 2, 3, 4, 5]
"""
for k, v in enumerate(items):
for i, val in enumerate(items[:k]):
if v < val:
items[i], items[i + 1:k + 1] = items[k], items[i:k]
break
return items
@given(st.lists(elements=st.integers()))
def test_insertionsort(x):
assert insertionsort(x) == sorted(x)
Selection Sort
def selectionsort(items):
"""
>>> selectionsort([])
[]
>>> selectionsort([1])
[1]
>>> selectionsort([1, 0])
[0, 1]
>>> selectionsort([2, 1, 0])
[0, 1, 2]
>>> selectionsort([1,2,3,4,5])
[1, 2, 3, 4, 5]
>>> selectionsort([4,5,3,1,2])
[1, 2, 3, 4, 5]
"""
for k in reversed(range(1, len(items))):
v, i = max((v, i) for i, v in enumerate(items[:k]))
if items[k] < v:
items[k], items[i] = items[i], items[k]
return items
@given(st.lists(elements=st.integers()))
def test_selectionsort(x):
assert selectionsort(x) == sorted(x)
Bubble Sort
def bubblesort(items):
"""
>>> bubblesort([])
[]
>>> bubblesort([1])
[1]
>>> bubblesort([1, 0])
[0, 1]
>>> bubblesort([2, 1, 0])
[0, 1, 2]
>>> bubblesort([1,2,3,4,5])
[1, 2, 3, 4, 5]
>>> bubblesort([4,5,3,1,2])
[1, 2, 3, 4, 5]
"""
for i in range(len(items)):
mod = False
for j in range(len(items) - 1):
if items[j + 1] < items[j]:
mod = True
items[j + 1], items[j] = items[j], items[j + 1]
if not mod: break
return items
@given(st.lists(elements=st.integers()))
def test_bubblesort(x):
assert bubblesort(x) == sorted(x)
Heap Sort
def siftup(items, i):
while i > 0:
p = (i - 1) // 2
if items[p] < items[i]:
items[p], items[i] = items[i], items[p]
i = p
return items
def siftdown(items, last):
p = 0
while p <= last:
l = 2 * p + 1
r = l + 1
max = p
if l <= last and items[max] <= items[l]: max = l
if r <= last and items[max] <= items[r]: max = r
if max == p: break
items[p], items[max] = items[max], items[p]
p = max
return items
def heapsort(items):
"""
>>> heapsort([])
[]
>>> heapsort([1])
[1]
>>> heapsort([1,2,3,4,5])
[1, 2, 3, 4, 5]
>>> heapsort([4,5,3,1,2])
[1, 2, 3, 4, 5]
"""
for i, t in enumerate(items):
items = siftup(items, i)
for i in reversed(range(len(items) - 1)):
items[i + 1], items[0] = items[0], items[i + 1]
items = siftdown(items, i)
return items
@given(st.lists(elements=st.integers()))
def test_heapsort(x):
assert heapsort(x) == sorted(x)
Merge Sort
def merge(left, right):
"""
>>> merge([2,4,6], [])
[2, 4, 6]
>>> merge([], [2,4,6])
[2, 4, 6]
>>> merge([1,3,6], [2,4,6])
[1, 2, 3, 4, 6, 6]
"""
if not left:
return right
elif not right:
return left
elif left[0] < right[0]:
return left[:1] + merge(left[1:], right)
else:
return right[:1] + merge(left, right[1:])
def mergesort(items):
"""
>>> mergesort([])
[]
>>> mergesort([1])
[1]
>>> mergesort([1,2,3,4,5])
[1, 2, 3, 4, 5]
>>> mergesort([4,5,3,1,2])
[1, 2, 3, 4, 5]
"""
if len(items) <= 1: return items
mid = len(items) // 2
left = mergesort(items[:mid])
right = mergesort(items[mid:])
return merge(left, right)
@given(st.lists(elements=st.integers()))
def test_mergesort(x):
assert mergesort(x) == sorted(x)
Quick Sort
def partition(items, begin, end, pivot):
f = begin + 1
l = end
while True:
while f <= l and items[f] <= pivot: f += 1
while f <= l and items[l] >= pivot: l -= 1
if f < l:
items[l], items[f] = items[f], items[l]
else:
break
items[l], items[begin] = items[begin], items[l]
return l
def qsort(items, fst, lst):
if fst >= lst: return
pivot = items[fst]
l = partition(items, fst, lst, pivot)
qsort(items, fst, l - 1)
qsort(items, l + 1, lst)
def quicksort(items):
"""
>>> quicksort([])
[]
>>> quicksort([1])
[1]
>>> quicksort([1,2,3,4,5])
[1, 2, 3, 4, 5]
>>> quicksort([4,5,3,1,2])
[1, 2, 3, 4, 5]
>>> quicksort([0, 0, 0, 1, 0, 0, 0])
[0, 0, 0, 0, 0, 0, 1]
"""
if not items: return items
qsort(items, 0, len(items) - 1)
return items
@given(st.lists(elements=st.integers()))
def test_quicksort(x):
assert quicksort(x) == sorted(x)
Shell Sort
def sort_gap(items, start, gap):
for k in range(len(items) - 1, 0, -1 * gap):
v, i = max((v, i) for i, v in enumerate(items[:k:gap]))
if items[k] < v:
items[k], items[i] = items[i], items[k]
def shellsort(items):
"""
>>> shellsort([])
[]
>>> shellsort([1])
[1]
>>> shellsort([1,2,3,4,5])
[1, 2, 3, 4, 5]
>>> shellsort([4,5,3,1,2])
[1, 2, 3, 4, 5]
"""
gap = len(items) // 2
while gap > 0:
for i in range(gap):
sort_gap(items, i, gap)
gap = gap // 2
return items
@given(st.lists(elements=st.integers()))
def test_shellsort(x):
assert shellsort(x) == sorted(x)
Hypothesis Tests
if __name__ == '__main__':
test_selectionsort()
test_bubblesort()
test_insertionsort()
test_quicksort()
test_mergesort()
test_heapsort()
test_shellsort()
doctest.testmod(verbose=True)
