sorting/efficient.py at master · CxdInitial/sorting · 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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
def heap_sort(elements):
    """
    Use the simple heap sort algorithm to sort the :param elements.
    :param elements: a sequence in which the function __get_item__ and __len__ were implemented
    :return: the sorted elements in increasing order
    """
    length = len(elements)
    if not length or length == 1:
        return elements
    for offset in range(0, length - 1):
        origin_parent = (length - offset - 2) / 2
        if origin_parent >= 0:
            left = origin_parent * 2 + 1 + offset
            right = left + 1
            parent = origin_parent + offset
            if right >= length:
                if elements[parent] > elements[left]:
                    elements[parent], elements[left] = elements[left], elements[parent]
            else:
                min_index = left
                if elements[right] < elements[left]:
                    min_index = right
                if elements[parent] > elements[min_index]:
                    elements[parent], elements[min_index] = elements[min_index], elements[parent]
            origin_parent -= 1
        while origin_parent >= 0:
            left = origin_parent * 2 + 1 + offset
            right = left + 1
            parent = origin_parent + offset
            min_index = left
            if elements[right] < elements[left]:
                min_index = right
            if elements[parent] > elements[min_index]:
                elements[parent], elements[min_index] = elements[min_index], elements[parent]
            origin_parent -= 1
    return elements


def merge_sort(elements):
    """
    Use the simple merge sort algorithm to sort the :param elements.
    :param elements: a sequence in which the function __get_item__ and __len__ were implemented,
    as well as the slice and add operations.
    :return: the sorted elements in increasing order
    """
    length = len(elements)
    if not length or length == 1:
        return elements
    volume = 2
    while length > volume / 2:
        index = 0
        while length - index >= volume:
            tmp = []
            i, j, limit = index, index + volume / 2, index + volume
            mid_limit = j
            while i < mid_limit and j < limit:
                if elements[j] < elements[i]:
                    tmp.append(elements[j])
                    j += 1
                else:
                    tmp.append(elements[i])
                    i += 1
            if i < mid_limit:
                tmp += elements[i:mid_limit]
            else:
                tmp += elements[j:limit]
            for value in tmp:
                elements[index] = value
                index += 1
        if length - index > volume / 2:
            tmp = []
            i, j = index, index + volume / 2
            mid_limit = j
            while i < mid_limit and j < length:
                if elements[j] < elements[i]:
                    tmp.append(elements[j])
                    j += 1
                else:
                    tmp.append(elements[i])
                    i += 1
            if i < mid_limit:
                tmp += elements[i:mid_limit]
            else:
                tmp += elements[j:]
            for value in tmp:
                elements[index] = value
                index += 1
        volume *= 2
    return elements


def quick_sort(elements):
    """
    Use the simple non-recursive quick sort algorithm to sort the :param elements.
    :param elements: a sequence in which the function __get_item__, __len__ and insert were implemented
    :return: the sorted elements in increasing order
    """
    length = len(elements)
    if not length or length == 1:
        return elements
    stack, limit = [], [0, length - 1]
    while stack or limit[1] - limit[0] > 0:
        while limit[1] - limit[0] > 0:
            i, j, tail = limit[0], limit[1] - 1, limit[1]
            if tail - i == 1:
                if elements[tail] > elements[i]:
                    i = tail
            else:
                while i < j:
                    while i < j and elements[i] <= elements[tail]:
                        i += 1
                    while j > i and elements[j] >= elements[tail]:
                        j -= 1
                    if i < j:
                        elements[i], elements[j] = elements[j], elements[i]
                        i += 1
                        j -= 1
            if i == j:
                if elements[i] < elements[tail]:
                    i += 1
                elif elements[i] > elements[tail]:
                    i = j
            elements[i], elements[tail] = elements[tail], elements[i]
            limit.append(i)
            stack.append(limit)
            limit = [limit[0], limit[2] - 1]
        if stack:
            top = stack.pop()
            limit = [top[2] + 1, top[1]]
    return elements