Basic sorting in Python

Question

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)

Answer 1

Your code looks nice and well tested: congratulations. I have a few comments anyway.

A little design/API comment

Compare sorted:

sorted(iterable[, key][, reverse])

Return a new sorted list from the items in iterable.

and list.sort:

sort(*, key=None, reverse=None)

This method sorts the list in place[...] it does not return the sorted sequence.

The difference is that one operates in place and the other one returns a new list. Your code does both which is likely to be confusing.

Other various comments

You could (and probably should) pass the sorting function as a parameter to your testing function. You'd have something like :

@given(st.lists(elements=st.integers()))
def test_sort(x, my_sorted):
 assert my_sorted(x) == sorted(x)

and :

for s in [selection, bubble, insertion, quicksort, mergesort, heapsort, shellsort]:
 test_sort(s)

---

The variable name mod might a bit confusing as one might think about the modulo operator. I guess modif or change would be better.

Suggestion

It might be worth defining a swap(i, j) function/method but it might affect performances.