Sorting/test_counting.py at master · ankit0504/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
import random

def counting_sort(arr):
    if len(arr) < 2:
        return arr
    minimum = min(arr)
    maximum = max(arr)
    num_instances = [0 for i in range(minimum, maximum+1)]
    returnable = [0 for i in range(len(arr))]
    for num in arr:
        num_instances[num - minimum] += 1
    for i in range(1, len(num_instances)):
        num_instances[i] += num_instances[i - 1]
    for i in reversed(arr):
        returnable[num_instances[i - minimum] - 1] = i
        num_instances[i - minimum] -= 1
    return returnable


def test_empty_list():
    assert counting_sort([]) == []


def test_one_element_list():
    rand_num = random.randint(0, 100)
    assert counting_sort([rand_num]) == [rand_num]


def test_already_sorted():
    already_sorted = [i for i in range(100)]
    assert counting_sort(already_sorted) == sorted(already_sorted)


def test_decrementing():
    decrementing = [i for i in reversed(range(100))]
    assert counting_sort(decrementing) == sorted(decrementing)


def test_random_positives():
    rand_nums = random.sample(range(1, 250), 100)
    assert counting_sort(rand_nums) == sorted(rand_nums)


def test_random_negatives():
    rand_nums = random.sample(range(-250, -1), 100)
    assert counting_sort(rand_nums) == sorted(rand_nums)


def test_random_numbers():
    rand_nums = random.sample(range(-250, 250), 100)
    assert counting_sort(rand_nums) == sorted(rand_nums)


def test_has_duplicates():
    rand_nums = [random.randint(0, 24) for x in range(100)]
    assert counting_sort(rand_nums) == sorted(rand_nums)