python-dsa/simple_quicksort.py at main · cornelmarck/python-dsa · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
"""Quicksort

Simple quicksort with non-random partioning
"""


def sort(items: list, key=lambda x: x):
    _recursive_sort(items, 0, len(items) - 1, key)


def _recursive_sort(items, begin, end, key):
    if begin >= end:
        return

    partition = _partition(items, begin, end, key)
    _recursive_sort(items, begin, partition - 1, key)
    _recursive_sort(items, partition + 1, end, key)


def _partition(items, begin, end, key) -> int:
    mid = (begin + end) // 2
    if items[mid] < items[begin]:
        _swap(items, begin, mid)
    if items[end] < items[begin]:
        _swap(items, begin, end)
    if items[mid] < items[end]:
        _swap(items, mid, end)
    pivot = items[end]

    i = begin
    for j in range(begin, end):
        if key(items[j]) <= key(pivot):
            _swap(items, i, j)
            i += 1
    _swap(items, i, end)
    return i


def _swap(items, idx_1, idx_2):
    tmp = items[idx_1]
    items[idx_1] = items[idx_2]
    items[idx_2] = tmp