Sorts

Insetion Sort

The insertion sort algorithm iterates through an input array and removes one element per iteration, finds the place the element belongs in the array, and then places it there. This process grows a sorted list from left to right. The algorithm is as follows:

To sort an array of size n in ascending order:

1. Iterate from arr[1] to arr[n] over the array.

2. Compare the current element (key) to its predecessor.

3. If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

The key is that: arr[i - 1] is always sorted.

Implementation

def insertion_sort(lst):
    # assume len(lst) > 1
    for i in range(1, len(lst)):
        # swap lst[i - 1] and lst[i] if lst[i - 1] > lst[i]
        # we stop at i < 1 because we know arr[0] is the smallest
        while (i >= 1) and (lst[i] < lst[i - 1]):
            val = lst[i]
            lst[i] = lst[i - 1]
            lst[i - 1] = val
            i = i - 1
    
    return lst

Merge Sort

Mergesort has two steps: merging and sorting. The algorithm uses a divide-and-conquer approach to merge and sort a list.

Divide and conquer is a technique used for breaking algorithms down into subproblems, solving the subproblems, and then combining the results back together to solve the original problem. It can be helpful to think of this method as divide, conquer, and combine.

The mergesort algorithm focuses on how to merge together two pre-sorted arrays such that the resulting array is also sorted. Mergesort can be implemented either recursively or iteratively.

Here is the recursive mergesort algorithm:

1. If the list has only one element, return the list and terminate. (Base case)
2. Split the list into two halves that are as equal in length as possible. (Divide)
3. Using recursion, sort both lists using mergesort. (Conquer)
4. Merge the two sorted lists and return the result. (Combine)

The merge step:

1. Create an empty list called the result list.
2. Do the following until one of the input lists is empty: Remove the first element of the list that has a lesser first element and append it to the result list.
3. When one of the lists is empty, append all elements of the other list to the result.

def merge_sort(lst):
    # base case
    if len(lst) == 1:
        return lst
    else:
        sorted_lst = []
        mid = len(lst) // 2
        left_lst = merge_sort(lst[:mid])
        right_lst = merge_sort(lst[mid:])
        # left_lst and right_lst will return two sorted lists, so we need to merge them
        # if left_lst[0] > right_lst[0], we remove first element from right_lst and append to 
        # the sorted_lst, if one of the lst is empty, we extend the another list to sorted_lst and exist the loop
        while left_lst or right_lst:
            if not left_lst or not right_lst:
                sorted_lst.extend(left_lst)
                sorted_lst.extend(right_lst)
                break
            elif left_lst[0] > right_lst[0]:
                sorted_lst.append(right_lst.pop(0))
            else:
                sorted_lst.append(left_lst.pop(0))
        
        return sorted_lst

Bubble Sort

Bubble sort is a simple, inefficient sorting algorithm used to sort lists. The Bubble sort algorithm compares each pair of elements in an array and swaps them if they are out of order until the entire array is sorted. For each element in the list, the algorithm compares every pair of elements.

The bubble sort algorithm is as follows:

1. Compare A[0] and A[1]. If A[0] is bigger than A[1], swap the elements.
2. Move to the next element, A[1] (which might now contain the result of a swap from the previous step), and compare it with A[2]. If A[1] is bigger than A[2], swap the elements. Do this for every pair of elements until the end of the list.
3. Do steps 1 and 2 n times.

def bubble_sort(lst):
    for _ in range(len(lst)):
        for j in range(len(lst) - 1):
            if lst[j] > lst[j + 1]:
                val = lst[j]
                lst[j] = lst[j + 1]
                lst[j + 1] = val
    
    return lst

Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array. 1. The subarray which is already sorted. 2. Remaining subarray which is unsorted. In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

We perform the steps given below until the unsorted subarray becomes empty:

1. Pick the minimum element from the unsorted subarray.
2. Swap it with the leftmost element of the unsorted subarray.
3. Now the leftmost element of unsorted subarray becomes a part (rightmost) of sorted subarray and will not be a part of unsorted subarray.

def bubble_sort(lst):
    
    def find_min(start):
        l, r = start, len(lst) - 1
        curr_min, index = (lst[l], l) if lst[l] < lst[r] else (lst[r], r)
        while l <= r:
            if lst[l] < curr_min:
                curr_min = lst[l]
                index = l
            if lst[r] < curr_min:
                curr_min = lst[r]
                index = r
            
            l += 1
            r -= 1
        
        return index
    
    for i in range(len(lst)):
        min_index = find_min(i)
        val = lst[i]
        lst[i] = lst[min_index]
        lst[min_index] = val
    
    return lst

Quick Sort

Quicksort uses divide and conquer to sort an array. Divide and conquer is a technique used for breaking algorithms down into subproblems, solving the subproblems, and then combining the results back together to solve the original problem. It can be helpful to think of this method as divide, conquer, and combine. Divide:

1. Pick a pivot element, A[q].
2. Partition, or rearrange, the array into two subarrays: A[p,…,q−1] such that all elements are less than A[q], and A[q+1,…,r] such that all elements are greater than or equal to A[q].
3. Conquer: Sort the subarrays A[p,…,q−1] and A[q+1,…,r] recursively with quicksort.
4. Combine: No work is needed to combine the arrays because they are already sorted.

Here is a recursive algorithm for quicksort:

1. If the list is empty, return the list and terminate. (Base case)
2. Choose a pivot element in the list.
3. Take all of the elements that are less than or equal to the pivot and use quicksort on them. (skip pivot, otherwise [5, 5, 5] will not reach base case)
4. Take all of the elements that are greater than the pivot and use quicksort on them.
5. Return the concatenation of the quicksorted list of elements that are less than or equal to the pivot, the pivot, and the quicksorted list of elements that are greater than the pivot.

def quick_sort(lst):
    if len(lst) <= 1:
        return lst
    else:
        mid = len(lst) // 2
        small_lst = []
        large_lst = []
        for i in range(len(lst)):
            if i != mid:
                if lst[i] >= lst[mid]:
                    large_lst.append(lst[i])
                else:
                    small_lst.append(lst[i])
            
        
        left_lst = quick_sort(small_lst)
        right_lst = quick_sort(large_lst)
        
        return left_lst + [lst[mid]] + right_lst

Heap Sort

Recall that, a root of the max heap is the maximum item in the array \(A[1 ... A.heap\_size]\). if we do a build_max_heap on entire \(A\), swap \(A[1]\) with \(A[n]\) and then do a max_heapify(A[1 ... n - 1], i), we end up with a sorted array.

For more detail please see Heaps

def heap_sort(A):
    build_max_heap(A)
    while A.heap_size >= 2:
        A[0], A[heap_size - 1] = A[heap_size - 1], A[0]
        A.heap_size = A.heap_size - 1
        max_heapify(A, 0)

Reference

https://lamfo-unb.github.io/2019/04/21/Sorting-algorithms/

https://brilliant.org/wiki/sorting-algorithms/#sorting-algorithms