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)):
        key = inp_list[index]
        position = index

        while position > 0 and inp_list[position-1] > key:
            # shift greater items to the left
            inp_list[position] = inp_list[position-1]
            position -= 1

        inp_list[position] = key
    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

Selection Sort

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
"""Selection Sort"""


def selection_sort(array: list) -> list:
    """Selection Sort"""
    for index in range(len(array)):
        minimum_number_index = index
        for index_2 in range(index+1, len(array)):
            if array[index_2] < array[minimum_number_index]:
                minimum_number_index = index_2
        if minimum_number_index != index:
            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"