# 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" ```