Algorithms/Sorting algorithms/comb sort.py at master · Panda-Lewandowski/Algorithms · 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import random
import time

N = 100000


def std_comb_sort(x):
    gap = len(x)
    swaps = True
    while gap > 1 or swaps:
        gap = max(1, int(gap / 1.25))  # minimum gap is 1
        swaps = False
        for i in range(len(x) - gap):
            j = i+gap
            if x[i] > x[j]:
                x[i], x[j] = x[j], x[i]
                swaps = True

    return x


def opt_comb_sort(x):
    l = len(x)
    gap = (l * 10 // 13) if l > 1 else 0
    while gap:
        if 8 < gap < 11:  ## variant "comb-11"
            gap = 11
        swapped = False
        for i in range(l - gap):
            if x[i + gap] < x[i]:
                x[i], x[i + gap] = x[i + gap], x[i]
                swapped = True
        gap = (gap * 10 // 13) or swapped

    return x


if __name__ == "__main__":
    a = []
    b = []
    c = []
    for i in range(N):
        a.append(i)
        b.append(N-i)
        c.append(random.randint(-N, N))

    print("NO OPTIMIZED std_comb_sort(x)")

    print("\n...SORTING ARRAY...")
    st = time.time()
    na = std_comb_sort(a)
    end = time.time()
    print("\nTIME:", (end - st), "  sec")

    print("\n...REVERSE ARRAY...")
    st = time.time()
    nb = std_comb_sort(b)
    end = time.time()
    print("\nTIME:", (end - st), "  sec")

    print("\n...RANDOM ARRAY...")
    st = time.time()
    nc = std_comb_sort(c)
    end = time.time()
    print("\nTIME:", (end - st), "  sec")

    print("\n\nOPTIMIZED opt_comb_sort(x)")

    print("\n...SORTING ARRAY...")
    st = time.time()
    na = opt_comb_sort(a)
    end = time.time()
    print("\nTIME:", (end - st), "  sec")

    print("\n...REVERSE ARRAY...")
    st = time.time()
    nb = opt_comb_sort(b)
    end = time.time()
    print("\nTIME:", (end - st), "  sec")

    print("\n...RANDOM ARRAY...")
    st = time.time()
    nc = opt_comb_sort(c)
    end = time.time()
    print("\nTIME:", (end - st), "  sec")