sorting/distribution.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
def counting_sort(elements):
    """
    Use the simple counting sort algorithm to sort the :param elements.
    :param elements: a integer 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
    mini = maxi = elements[0]
    for element in elements:
        assert isinstance(element, int)
        if element < mini:
            mini = element
        if element > maxi:
            maxi = element
    all_range = []
    for i in range(maxi - mini + 1):
        all_range.append(0)
    for element in elements:
        all_range[element - mini] += 1
    length = 0
    for i in range(len(all_range)):
        count = all_range[i]
        while count > 0:
            elements[length] = i + mini
            length += 1
            count -= 1
    return elements


def bucket_sort(elements, bucket_size=10):
    """
    Use the simple bucket sort algorithm to sort the :param elements.
    :param bucket_size: the distribution buckets' size
    :param elements: a integer 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
    mini = maxi = elements[0]
    for element in elements:
        assert isinstance(element, int)
        if element < mini:
            mini = element
        if element > maxi:
            maxi = element
    buckets_size = (maxi - mini + 1) // bucket_size
    if (maxi - mini + 1) % bucket_size:
        buckets_size += 1
    buckets = []
    for i in range(buckets_size):
        buckets.append([None, None])
    for element in elements:
        index = element // bucket_size
        ptr = buckets[index]
        while ptr[1] and ptr[1][0] < element:
            ptr = ptr[1]
        element = [element, ptr[1]]
        ptr[1] = element
    length = 0
    for bucket in buckets:
        ptr = bucket[1]
        while ptr:
            elements[length] = ptr[0]
            length += 1
            ptr = ptr[1]
    return elements


def radix_sort(elements):
    """
    Use the simple radix sort algorithm to sort the :param elements.
    :param bucket_size: the distribution buckets' size
    :param elements: a integer 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
    maxi = elements[0]
    for element in elements:
        assert isinstance(element, int)
        if element > maxi:
            maxi = element
    bits = 0
    while maxi > 0:
        maxi //= 10
        bits += 1
    all_range = [[], [], [], [], [], [], [], [], [], []]
    for i in range(2):
        for element in elements:
            num = (element // (10 ** i)) % 10
            all_range[num].append(element)
        length = 0
        for items in all_range:
            while items:
                elements[length] = items.pop(0)
                length += 1
    return elements