Show understanding of insertion sort and bubble sort methods

19.1 Algorithms – Sorting Basics 📚

Insertion Sort – Like Sorting Playing Cards

Insertion sort builds the final sorted array one item at a time. Imagine you’re sorting a hand of playing cards: you pick up each card and insert it into its correct position among the cards already sorted. The algorithm is simple, stable, and great for small or nearly sorted lists.

1. Start with the second element (index 1) as the “current” item.
2. Compare it with the elements to its left.
3. Shift larger elements one position to the right.
4. Insert the current item into the vacated spot.
5. Move to the next element and repeat until the list is sorted.

Pseudocode:

for i = 1 to n-1 do
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key do
        A[j+1] = A[j]
        j = j - 1
    end while
    A[j+1] = key
end for

Example: Sort the array [8, 3, 5, 4, 6] step‑by‑step.

Complexity: $O(n^2)$ in the worst case, $O(n)$ best case (already sorted). Space complexity is $O(1)$; it’s an in‑place algorithm. It’s stable – equal elements keep their relative order.

Bubble Sort – Like Bubbles Rising to the Surface

Bubble sort repeatedly steps through the list, compares adjacent items, and swaps them if they’re in the wrong order. Think of a pot of hot chocolate: the biggest “bubbles” (largest numbers) rise to the top after each pass. It’s easy to understand but not very efficient for large lists.

1. Start at the beginning of the array.
2. Compare each pair of adjacent items.
3. Swap if the left item is greater than the right.
4. After one full pass, the largest item “bubbles” to the end.
5. Repeat the process for the remaining unsorted portion.

Pseudocode:

for i = 0 to n-2 do
    for j = 0 to n-2-i do
        if A[j] > A[j+1] then
            swap A[j] and A[j+1]
        end if
    end for
end for

Example: Sort the array [4, 1, 3, 2] step‑by‑step.

Complexity: $O(n^2)$ in all cases. Space complexity is $O(1)$; it’s an in‑place algorithm. Bubble sort is also stable.

Key Takeaway: Both insertion sort and bubble sort are simple to implement and understand, but they’re best suited for small or nearly sorted datasets. For larger data, more efficient algorithms like quicksort or mergesort are preferred. 🚀