qsort.py test.py

qsort.py test.py

$ cat qsort.py
def qsort(iterable, start=0, end=None):
    if end is None:
        end = len(iterable) - 1

    if hasattr(iterable, 'encode'):
        iterable = list(iterable)

    if start >= end:
        return iterable

    new_pivot_index = partition(iterable, start, end)

    qsort(iterable, start, new_pivot_index - 1)
    qsort(iterable, new_pivot_index + 1, end)

    return iterable


def partition(iterable, start, end):
    pivot, original_pivot_index = pivot_choice(iterable, start, end)
    pivot_index = start

    for index in range(start, end + 1):
        if(
            index == original_pivot_index
            or iterable[index] > pivot
        ):
            continue

        iterable[pivot_index], iterable[index] = (
            iterable[index], iterable[pivot_index]
        )

        if pivot_index == original_pivot_index:
            original_pivot_index = index

        pivot_index += 1

    iterable[pivot_index], iterable[original_pivot_index] = (
        iterable[original_pivot_index], iterable[pivot_index]
    )

    return pivot_index


def pivot_choice(iterable, start, end):
    pivot_index = int((end - start) / 2 + start)
    return (
        iterable[pivot_index],
        pivot_index
    )

$ cat test.py
from hypothesis import given
from hypothesis.strategies import floats, integers, lists, characters

from qsort import qsort


def test_simpler():
    test_values = list(reversed(range(5)))
    assert qsort(test_values[:]) == sorted(test_values[:])

def test_simple():
    test_values = list(reversed(range(7)))
    assert qsort(test_values[:]) == sorted(test_values[:])

def test_medium():
    test_values = list(reversed(range(9)))
    assert qsort(test_values[:]) == sorted(test_values[:])

def test_medium_plus():
    test_values = list(reversed(range(12)))
    assert qsort(test_values[:]) == sorted(test_values[:])

def test_large():
    test_values = list(reversed(range(100)))
    assert qsort(test_values[:]) == sorted(test_values[:])

def test_larger():
    test_values = list(reversed(range(1000)))
    assert qsort(test_values[:]) == sorted(test_values[:])

def test_big():
    test_values = list(reversed(range(10_000)))
    assert qsort(test_values[:]) == sorted(test_values[:])

def test_bigger():
    test_values = list(reversed(range(100_000)))
    assert qsort(test_values[:]) == sorted(test_values[:])

def test_huge():
    test_values = list(reversed(range(1_000_000)))
    assert qsort(test_values[:]) == sorted(test_values[:])

@given(lists(integers()))
def test_hypothesis_integers(test_values):
    assert qsort(test_values[:]) == sorted(test_values)

@given(lists(floats(allow_nan=False)))
def test_hypothesis_floats(test_values):
    assert qsort(test_values[:]) == sorted(test_values)

@given(characters())
def test_hypothesis_characters(test_values):
    assert qsort(test_values[:]) == sorted(test_values)