sort.py

from random import randint
from time import time


def swap(array, i, j):
    array[i], array[j] = array[j], array[i]


def bubble(array):
    n = len(array)
    for i in range(n - 1):
        for j in range(i + 1, n):
            if array[i] > array[j]:
                swap(array, i, j)


def select(array):
    n = len(array)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if array[j] < array[min_index]:
                min_index = j

        swap(array, min_index, i)


def insert(array):
    n = len(array)
    for i in range(1, n):
        tmp = array[i]
        for j in range(i, -1, -1):
            if j > 0 and tmp < array[j - 1]:
                array[j] = array[j - 1]
                continue
            break
        array[j] = tmp


def shell(array):
    n = len(array)
    dist = n // 2
    while dist > 0:
        for i in range(dist, n):
            tmp = array[i]
            j = i
            while j >= dist and array[j - dist] > tmp:
                array[j] = array[j - dist]
                j -= dist
            array[j] = tmp
        dist //= 2


def sh_gap(array):
    # use Marcin Ciura's gap sequence
    gaps = [701, 301, 132, 57, 23, 10, 4, 1]
    for gap in gaps:
        for i in range(gap, len(array)):
            temp = array[i]
            j = i
            while j >= gap and array[j - gap] > temp:
                array[j] = array[j - gap]
                j -= gap

            array[j] = temp


def merge(array, start=0, end=None):
    if end is None:
        end = len(array)

    if end - start > 1:
        mid = (start + end) // 2
        merge(array, start, mid)
        merge(array, mid, end)
        merge_part(array, start, mid, end)

def merge_part(array, start, mid, end):
    left_len, right_len = mid - start, end - mid
    left, right = array[start:mid], array[mid:end]
    i = j = 0
    for k in range(start, end):
        if j >= right_len or (i < left_len and left[i] <= right[j]):
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1


def heap(array):
    n = len(array)

    def sink(k):
        while 2 * k + 1 < n:
            child = 2 * k + 1
            if child + 1 < n and array[child] < array[child + 1]:
                child += 1

            if array[k] > array[child]:
                break

            swap(array, k, child)
            k = child

    for k in range((n - 1) // 2, -1, -1):
        sink(k)

    while n > 0:
        swap(array, 0, n - 1)
        n -= 1
        sink(0)


def quick(array, start=0, end=None):
    if end is None:
        end = len(array) - 1

    if start >= end:
        return

    lt, gt = start, end
    pivot = array[start]
    i = start + 1
    while i <= gt:
        diff = array[i] - pivot
        if diff < 0:
            swap(array, i, lt)
            lt += 1
            i += 1
        elif diff > 0:
            swap(array, i, gt)
            gt -= 1
        else:
            i += 1

    quick(array, start, lt-1)
    quick(array, gt+1, end)


def test(func):
    array = [randint(0, 10) for _ in range(10)]
    print('========= {} =========='.format(func.__name__))
    print(array)
    result = sorted(array)
    func(array)
    print(array)
    if array != result:
        print('xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx')


if __name__ == '__main__':
    functions = [bubble, insert, select, shell, sh_gap, heap, quick, merge]
    
    # test
    for func in functions:
        test(func)

    # time cost
    cost = [0] * len(functions)
    for _ in range(100):
        for i, sort_func in enumerate(functions):
            array = [randint(1, 1000) for _ in range(1000)]
            t0 = time()
            sort_func(array)
            cost[i] += time() - t0

    for i, sort_func in enumerate(functions):
        print('{:6} :{:.6f}'.format(sort_func.__name__, cost[i]))