Sorting Algorithms Cheatsheet

Cheatsheet Content

Insertion Sort Concept: Builds the final sorted array (or list) one item at a time. It iterates through the input elements and inserts each element into its correct position in the sorted part of the array. Algorithm: for i from 1 to n-1: key = array[i] j = i - 1 while j >= 0 and key Example: Sorting $[5, 2, 4, 6, 1, 3]$ $[5, \underline{2}, 4, 6, 1, 3]$ -> $[2, 5, 4, 6, 1, 3]$ (2 inserted before 5) $[2, 5, \underline{4}, 6, 1, 3]$ -> $[2, 4, 5, 6, 1, 3]$ (4 inserted before 5) $[2, 4, 5, \underline{6}, 1, 3]$ -> $[2, 4, 5, 6, 1, 3]$ (6 already in place) $[2, 4, 5, 6, \underline{1}, 3]$ -> $[1, 2, 4, 5, 6, 3]$ (1 inserted at beginning) $[1, 2, 4, 5, 6, \underline{3}]$ -> $[1, 2, 3, 4, 5, 6]$ (3 inserted before 4) Bubble Sort Concept: Repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. Algorithm: for i from 0 to n-2: swapped = false for j from 0 to n-i-2: if array[j] > array[j+1]: swap(array[j], array[j+1]) swapped = true if not swapped: break Example: Sorting $[5, 1, 4, 2, 8]$ 1st Pass: $(5, 1) \to (1, 5)$ $[1, 5, 4, 2, 8]$ $(5, 4) \to (1, 4, 5, 2, 8)$ $(5, 2) \to (1, 4, 2, 5, 8)$ $(5, 8) \to (1, 4, 2, 5, 8)$ 2nd Pass: $(1, 4) \to (1, 4, 2, 5, 8)$ $(4, 2) \to (1, 2, 4, 5, 8)$ $(4, 5) \to (1, 2, 4, 5, 8)$ $(5, 8) \to (1, 2, 4, 5, 8)$ 3rd Pass: Array is already sorted, no swaps. Algorithm terminates. Quick Sort Concept: A divide-and-conquer algorithm. It picks an element as a pivot and partitions the array around the picked pivot. Algorithm (Lomuto Partition Scheme): function quickSort(array, low, high): if low Example: Sorting $[10, 80, 30, 90, 40, 50, 70]$ (pivot is last element) Initial: $[10, 80, 30, 90, 40, 50, 70]$ (pivot=70) Partition: Elements $\le 70$ are moved to left, others to right. $[10, 30, 40, 50, \underline{70}, 90, 80]$ (70 is at its final position) Recursively sort left sub-array $[10, 30, 40, 50]$ (pivot=50) $[10, 30, 40, \underline{50}]$ Recursively sort right sub-array $[90, 80]$ (pivot=80) $[\underline{80}, 90]$ Combine: $[10, 30, 40, 50, 70, 80, 90]$ Merge Sort Concept: A divide-and-conquer algorithm. It divides the unsorted list into $n$ sublists, each containing one element, and repeatedly merges sublists to produce new sorted sublists until there is only one sorted list. Algorithm: function mergeSort(array): if length(array) Example: Sorting $[38, 27, 43, 3, 9, 82, 10]$ Divide: $[38, 27, 43, 3]$ and $[9, 82, 10]$ Then further into single elements Merge: $[27, 38]$, $[3, 43]$ -> $[3, 27, 38, 43]$ $[9, 82]$, $[10]$ -> $[9, 10, 82]$ Finally merge $[3, 27, 38, 43]$ and $[9, 10, 82]$ Result: $[3, 9, 10, 27, 38, 43, 82]$ Heap Sort Concept: A comparison-based sorting technique based on the Binary Heap data structure. It's similar to selection sort where we first find the maximum element and place it at the end. Algorithm: function heapSort(array): n = length(array) // Build max heap for i from n/2 - 1 down to 0: heapify(array, n, i) // Extract elements one by one for i from n-1 down to 0: swap(array[0], array[i]) // Move current root to end heapify(array, i, 0) // Call max heapify on reduced heap function heapify(array, n, i): largest = i // Initialize largest as root left = 2 * i + 1 right = 2 * i + 2 // If left child is larger than root if left array[largest]: largest = left // If right child is larger than largest so far if right array[largest]: largest = right // If largest is not root if largest != i: swap(array[i], array[largest]) heapify(array, n, largest) Example: Sorting $[4, 10, 3, 5, 1]$ Build Max Heap: Initial: $[4, 10, 3, 5, 1]$ Heapify from last non-leaf node (index 1, value 10): $[4, 10, 3, 5, 1]$ becomes $[10, 5, 3, 4, 1]$ (after some swaps) Extract Max: Swap 10 (root) with 1 (last): $[1, 5, 3, 4, \underline{10}]$ Heapify remaining 4 elements: $[5, 4, 3, 1, \underline{10}]$ Swap 5 (root) with 1 (last of heap): $[1, 4, 3, \underline{5}, \underline{10}]$ Heapify remaining 3 elements: $[4, 3, 1, \underline{5}, \underline{10}]$ Continue until sorted: $[1, 3, 4, 5, 10]$