Sorting Algorithms

Bubble Sort

 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
"""Bubble sort implementation"""


def bubble_sort(array: list) -> list:
    """Uses bubble sort to sort a list"""
    # Bubble sort is a O(N**2) algorithm
    # First, assume the array is not sorted
    is_sorted = False
    # Now, fix the range until the end of the array
    unsorted_until = len(array) - 1
    # repeat until it is sorted
    while not is_sorted:
        # assume it is sorted
        is_sorted = True
        # loop through the range from 0 till the last sorted index.
        for index in range(unsorted_until):
            # Check current item with the next item.
            # This is safe to do because there's always one item ahead of this
            # this is because we use unsorted_until = len(array) -1, which
            # yields the index of the last item, but we also use
            # range(unsorted_until), which gives us an iterable from 0 *till*
            # that number, but not including it.  So even in the first trial,
            # we do not reach the end of the list.
            if array[index] > array[index+1]:
                # If the item is larger than the next item, *bubble* the
                # smaller one upwards.  Another way to think of bubble sort is
                # to think of it as *sinking* the largest item to the bottom of
                # the row at each trial.
                array[index], array[index+1] = array[index+1], array[index]
                # Now that a change has been made, you know that the list was
                # unsorted
                is_sorted = False
        # Reduce the sorting view to exclude the item.
        unsorted_until -= 1
    # return the item, note that this is not really necessary since we are
    # *modifying* the original item.
    return array


def test_bubble_sort():
    """Tests bubble sort"""
    import random
    array = [random.randint(0, 10000) for _ in range(5)]
    sorted_array = sorted(array)
    bubble_sorted_array = bubble_sort(array)
    assert bubble_sorted_array == sorted_array, "Bubble sorting failed"

Insertion Sort

 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
"""Insertion Sort"""


def insertion_sort(inp_list):
    """Insertion Sort
    O(n**2) sorting algorithm.
    This algorithm will assume that the left portion is sorted.
    At the beginning, the first item in the list is assumed to be sorted.
    Then, the first item of the unsorted portion is *inserted* into this
    sorted sublist at the right position.
    When this is done, the items in the sublist that are greater
    than this item are shifted to the right.
    """
    for index in range(1, len(inp_list)):
        position = index

        while position > 0 and inp_list[position] < inp_list[position-1]:
            # shift greater items to the left
            inp_list[position-1], inp_list[position] = (
                inp_list[position], inp_list[position-1]
            )
            position -= 1

    return inp_list


def binary_insertion_sort(inp_list):
    """Binary Insertion Sort.
    This is a modification of selection sort, wherein
    instead of comparing *all* items in the sorted list to the
    key value, we find the best place to put it.
    However, since the insertion will mandate the shifting of the numbers anyway,
    this will still take O(n**2).
    """


def test_insertion_sort():
    import random
    array = [random.randint(0, 1000) for _ in range(10)]
    sorted_array = sorted(array)
    insertion_sorted_array = insertion_sort(array)
    assert insertion_sorted_array == sorted_array, "Insertion sort failed"

Merge Sort

1
2
3
4
5
"""Merge Sort Algorithm"""


def merge_sort(input_list):
    return input_list

Selection Sort

 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
"""Selection Sort"""


def selection_sort(array: list) -> list:
    """Selection Sort"""
    # first, loop through the entire array
    for index in range(len(array)):
        # let's assume the *current* position
        # occupies the ith-smallest value (as in, the value is where it needs
        # to be.) This current position is marked as `minimum_number_index`
        minimum_number_index = index
        # loop through the next items in the array
        for index_2 in range(index+1, len(array)):
            # if the item at this index_2 is lesser than the item
            # in the `minimum_number_index` position, then *select*
            # this index as the `minimum_number_index`
            if array[index_2] < array[minimum_number_index]:
                minimum_number_index = index_2
        # if the `index` is not equal to the `minimum_value_index`,
        # this means our assumption was wrong,
        # and that we *selected* the appropriate value.
        if minimum_number_index != index:
            # Swap these values.
            array[index], array[minimum_number_index] = (
                array[minimum_number_index], array[index]
            )
    return array


def test_selection_sort():
    """Tests selection sort"""
    import random
    array = [random.randint(0, 10000) for _ in range(5)]
    sorted_array = sorted(array)
    bubble_sorted_array = selection_sort(array)
    assert bubble_sorted_array == sorted_array, "Selection sorting failed"