Сортировки вставками

#!/usr/bin/env python3

import time, random, os, math

shell_gaps = []


def shell_generate_gaps():
    global shell_gaps
    max_gap = int(os.environ.get("ALEN", "1000"))
    c3 = 1
    while c3 <= max_gap:
        c32 = c3
        while c32 <= max_gap:
            shell_gaps.append(c32)
            #- print("__: appended {}".format(c32))
            c32 *= 2
        c3 *= 3
    shell_gaps.sort(reverse = True)


def shell_sort(arr):
    n = len(arr)
    #- gaps = generate_gaps(n)
    for gap in shell_gaps:
        #print("__: gap={}".format(gap))
        #print("__: arr={}".format(arr))
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j-gap] > temp:
                arr[j] = arr[j-gap]
                j -= gap
            arr[j] = temp
    #print("__: final: arr={}".format(arr))


def comb_sort(arr):
    coeff = 0.8017118471377938
    n = len(arr)
    gap = n
    while True:
        if gap > 1:
            gap = int(gap*coeff)
        #- print("__: comb_sort: run for gap={}".format(gap))
        is_sorted = True
        for i in range(0, n - gap):
            if arr[i] > arr[i+gap]:
                temp = arr[i]
                arr[i] = arr[i+gap]
                arr[i+gap] = temp
                is_sorted = False
        if gap == 1 and is_sorted:
            break


def rec_qsort(arr, li, ri):
    while True: ## instead of recursion
        if ri <= li:
            return
        if ri - li < 10:
            for i in range(li+1, ri+1):
                temp = arr[i]
                j = i
                while j >= li+1 and arr[j-1] > temp:
                    arr[j] = arr[j-1]
                    j -= 1
                arr[j] = temp
            return
        si = random.randint(li, ri)
        temp = arr[li]
        arr[li] = arr[si]
        arr[si] = temp
        lp = li
        rp = ri
        leading_lp = True
        while lp < rp:
            cv = arr[lp] - arr[rp]
            if cv > 0:
                temp = arr[lp]
                arr[lp] = arr[rp]
                arr[rp] = temp
            if cv >= 0:
                leading_lp = not leading_lp
            if leading_lp:
                rp -= 1
            else:
                lp += 1
        if lp != rp:
            raise AssertionError('lp == rp')
        lwx = lp - li
        rwx = ri - rp
        if lwx > rwx:
            rec_qsort(arr, rp+1, ri)
            ri = lp - 1
        else:
            rec_qsort(arr, li, lp-1)
            li = rp+1


def qsort(arr):
    rec_qsort(arr, 0, len(arr) - 1)


def embedded_sort(arr):
    arr.sort()


def generate_array():
    arr_len = int(os.environ.get("ALEN", "1000"))
    akind = os.environ.get("AKIND", "almost_sorted")
    if akind == 'sorted':
        return [i for i in range(arr_len)]
    elif akind == 'reverse':
        return [arr_len-i for i in range(arr_len)]
    elif akind == 'almost_sorted':
        arr = []
        psize = min(int(math.sqrt(arr_len)), 1)
        while len(arr) < arr_len:
            psize1 = min(psize, arr_len - len(arr))
            curr_len = len(arr)
            portion = [i+curr_len+1 for i in range(psize1)]
            random.shuffle(portion)
            arr.extend(portion)
        return arr
    else:
        arr = [i for i in range(arr_len)]
        random.shuffle(arr)
        return arr


def run(sort_func):
    tsum = 0
    for arr in g_arrays:
        arrx = arr[:]
        t0 = time.time()
        sort_func(arrx)
        tsum += time.time() - t0
        for j in range(len(arrx) - 1):
            if arrx[j] > arrx[j+1]:
                print("__: unsorted: j={} a1={} a2={}".format(j, arr[j], arr[j+1]))
                raise RuntimeError("assertion: not sorted")
    return tsum


if __name__ == "__main__":
    shell_generate_gaps()
    g_arrays = [generate_array() for i in range(100)]
    print("shell_sort tsum:", run(shell_sort))
    print("comb_sort tsum:", run(comb_sort))
    print("qsort tsum:", run(qsort))
    print("embedded_sort tsum:", run(embedded_sort))