Bubble Sort

Bubble sort is a sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order, resulting in the largest unsorted elements “bubbling” to the top.

In Bubble sort, every iteration the biggest value is sent to the last. So we use an outer loop to keep track of what is already sorted decreasing from last index. And an inner loop that check from beginning until what is not sorted (outer loop index) and swaps the bigger value towards right.

def bubble_sort(array):
    for i in range(len(array) - 1, 0, -1):
        for j in range(0, i):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
    
    return array

Selection Sort

Selection sort is a sorting algorithm that divides the input list into a sorted and an unsorted region, repeatedly selecting the smallest (or largest) element from the unsorted region and moving it to the end of the sorted region.

In Selection sort, at each step, it selects the smallest element from the unsorted portion and swaps it with the first element in the unsorted portion, gradually building the sorted list. So, after k steps, first k values are sorted.

def selection_sort(array):
    for i in range(len(array)):
        min_index = -1
        min_value = float('inf')
        for j in range(i, len(array)):
            if array[j] < min_value:
                min_value = array[j]
                min_index = j
        
        array[i], array[min_index] = array[min_index], array[i]
    
    return array

Insertion Sort

Insertion sort is a sorting algorithm that builds a sorted array one element at a time by repeatedly taking the next unsorted element and inserting it into its correct position within the already sorted portion of the array.

This is an adaptive algorithm - Less time if more elements are sorted. And this can also work for streaming data (online processing)

def insertion_sort(array):
    for i in range(1, len(array)):
        for j in range(i, 0, -1):
            if array[j] < array[j - 1]:
                array[j], array[j - 1] = array[j - 1], array[j]
            else:
                break

    return array

Merge Sort

Merge sort is a divide-and-conquer sorting algorithm that recursively splits the input array into halves, sorts each half, and then merges the sorted halves back together to produce a fully sorted array. The base case for recursion is when the array size is 1 (low = high). The actual sorting takes in merge function. It takes two sorted arrays and then does a single loop to correctly place the elements in new array.

def merge_sort(array):
    def _merge_sort(arr, low, high):
        if low >= high:
            return

        mid = (low + high) // 2
        _merge_sort(arr, low, mid)
        _merge_sort(arr, mid + 1, high)

        _merge(arr, low, mid, high)

    def _merge(arr, low, mid, high):
        temp = []
        l = low
        r = mid + 1

        while l <= mid and r <= high:
            if (arr[l] <= arr[r]):
                temp.append(arr[l])
                l += 1
            else:
                temp.append(arr[r])
                r += 1
        
        while l <= mid:
            temp.append(arr[l])
            l += 1
        while r <= high:
            temp.append(arr[r])
            r += 1
        
        for i in range(low, high + 1):
            arr[i] = temp[i - low]

    _merge_sort(array, 0, len(array) - 1)
    return array

Quick Sort

Quick sort is an efficient sorting algorithm that uses a divide-and-conquer approach by selecting a ‘pivot’ element, partitioning the array into elements less than and greater than the pivot, and recursively sorting the partitions.

def quick_sort(array):
    def _sort(arr, low, high):
        pivot = arr[low]
        l = low + 1
        r = high

        while True:

            while l <= r and arr[l] <= pivot:
                l += 1

            while l <= r and arr[r] > pivot:
                r -= 1

            if l >= r:
                break
        
            arr[l], arr[r] = arr[r], arr[l]

        arr[low], arr[r] = arr[r], arr[low]

        return r

    def _quick_sort(arr, low, high):
        if low >= high:
            return
        partition = _sort(arr, low, high)
        _quick_sort(arr, low, partition - 1)
        _quick_sort(arr, partition + 1, high)

    _quick_sort(array, 0, len(array) - 1)
    return array

Properties

	Complexity	In-place	Stable	No of swaps	No of comparisons
Bubble Sort	$O(n^2)$	True	True	$O(n^2)$	$O(n^2)$
Selection Sort	$O(n^2)$	True	False	$O(n)$	$O(n^2)$
Insertion Sort	$O(n^2)$	True	True	$O(n^2)$	$O(n^2)$
Merge Sort	$O(n \log n)$	False $O(n)$	True	Nil	$O(n \log n)$
Quick Sort	$O(n log n)$	True	False	Depends on pivot	Depends on pivot