Sorting Algorithms

Sorting: • Sorting is the process of arranging items in a sequence in a particular order — ascending (smallest to largest) or descending. • Sorting is fundamental in computer science — it improves search efficiency and is used in databases, file systems, and countless algorithms. Bubble Sort: • Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. • After each pass through the array, the largest unsorted element 'bubbles up' to its correct position at the end. • Requires n-1 passes for an array of n elements. Algorithm: For i from 0 to n-2: # outer loop — controls passes For j from 0 to n-2-i: # inner loop — controls comparisons If arr[j] > arr[j+1]: Swap arr[j] and arr[j+1] Python Implementation: def bubble_sort(arr): n = len(arr) for i in range(n - 1): swapped = False for j in range(n - 1 - i): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True if not swapped: # optimisation: stop if no swaps in a pass break return arr print(bubble_sort([64, 25, 12, 22, 11])) # Output: [11, 12, 22, 25, 64] Trace for [64, 25, 12, 22, 11]: Pass 1: [25,12,22,11,64] — 64 moves to end Pass 2: [12,22,11,25,64] — 25 moves to correct position Pass 3: [12,11,22,25,64] — 22 correct Pass 4: [11,12,22,25,64] — sorted Time Complexity: • Best case (already sorted): O(n) — with the swapped optimisation • Average case: O(n²) • Worst case (reverse sorted): O(n²) Space Complexity: O(1) — in-place sorting Bubble sort is simple to understand but inefficient for large datasets.

Insertion Sort: • Insertion sort builds the sorted array one element at a time by inserting each new element into its correct position in the already-sorted portion. • Analogy: Sorting a hand of playing cards — you pick up one card at a time and insert it in the right place among the cards you already hold. Algorithm: • Divide the array conceptually into a sorted left portion (initially just the first element) and an unsorted right portion. • For each element in the unsorted portion: 1. Store it as 'key'. 2. Compare key with elements in the sorted portion from right to left. 3. Shift elements greater than key one position to the right. 4. Insert key in the correct position. Python Implementation: def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] # element to be placed j = i - 1 # Move elements greater than key one position ahead while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key # insert key in correct position return arr print(insertion_sort([12, 11, 13, 5, 6])) # Output: [5, 6, 11, 12, 13] Trace for [12, 11, 13, 5, 6]: i=1: key=11 → [11, 12, 13, 5, 6] i=2: key=13 → [11, 12, 13, 5, 6] (no change) i=3: key=5 → [5, 11, 12, 13, 6] i=4: key=6 → [5, 6, 11, 12, 13] Time Complexity: • Best case (already sorted): O(n) — only one comparison per element, no shifts. • Average case: O(n²) • Worst case (reverse sorted): O(n²) Space Complexity: O(1) — in-place When is Insertion Sort more efficient? 1. Small datasets: For very small arrays (n < 20), insertion sort is fast in practice due to low overhead. 2. Nearly sorted arrays: When the array is almost sorted, insertion sort runs close to O(n) — far better than bubble sort's worst case behaviour. 3. Online sorting: When elements arrive one at a time and must be sorted as they arrive, insertion sort is ideal. 4. In practice: Many real-world libraries (like Python's Timsort) use insertion sort for small subarrays within larger divide-and-conquer algorithms.

Selection Sort: • Selection sort repeatedly finds the minimum element in the unsorted portion and swaps it to its correct position at the beginning of the unsorted portion. • After each pass, the sorted portion grows by one element. Algorithm: For i from 0 to n-2: Find the index of the minimum element in arr[i..n-1] Swap arr[i] with arr[min_index] Python Implementation: def selection_sort(arr): n = len(arr) for i in range(n - 1): min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr print(selection_sort([64, 25, 12, 22, 11])) # Output: [11, 12, 22, 25, 64] Trace for [64, 25, 12, 22, 11]: Pass 1: min=11 at index 4 → swap with index 0 → [11, 25, 12, 22, 64] Pass 2: min=12 at index 2 → swap with index 1 → [11, 12, 25, 22, 64] Pass 3: min=22 at index 3 → swap with index 2 → [11, 12, 22, 25, 64] Pass 4: min=25 at index 3 → no swap needed → [11, 12, 22, 25, 64] Time Complexity: O(n²) for all cases (best, average, worst) — always makes the same number of comparisons. Space Complexity: O(1) — in-place. Key property: Makes at most n-1 swaps — useful when write operations are costly. Comparison of Three Sorting Algorithms: | Feature | Bubble Sort | Insertion Sort | Selection Sort | |---------------------|---------------------|---------------------|---------------------| | Best Case | O(n) with opt. | O(n) | O(n²) | | Average Case | O(n²) | O(n²) | O(n²) | | Worst Case | O(n²) | O(n²) | O(n²) | | Space | O(1) | O(1) | O(1) | | Number of Swaps | O(n²) worst case | O(n²) worst case | O(n) — at most n-1 | | Stable? | Yes | Yes | No (basic version) | | Best for | Nearly sorted data | Nearly sorted data | Minimising writes | Stability: A stable sort preserves the relative order of equal elements. Bubble and Insertion sort are stable; basic Selection sort is not. All three are O(n²) — unsuitable for large datasets. Advanced algorithms (Merge Sort O(n log n), Quick Sort O(n log n) average) are used in practice.