3
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.