Show understanding of the insertion sort and bubble sort methods, including their operation, efficiency and typical use‑cases.
Insertion Sort
Insertion sort builds the final sorted list one element at a time. It is similar to the way many people sort a hand of playing cards.
Algorithm description
Assume the first element of the array is a sorted sub‑array of length 1.
Take the next element (the “key”) and compare it with elements in the sorted sub‑array moving from right to left.
Shift each larger element one position to the right.
Insert the key into the first position that is not larger than it.
Repeat steps 2‑4 for each element until the whole array is sorted.
Pseudocode
for i = 1 to n‑1
key = A[i]
j = i‑1
while j ≥ 0 and A[j] > key
A[j+1] = A[j]
j = j‑1
A[j+1] = key
Complexity analysis
Best case (already sorted): \$T_{\text{best}}(n) = \Theta(n)\$ – only one comparison per element.
Worst and average case: \$T{\text{worst}}(n) = T{\text{avg}}(n) = \Theta(n^{2})\$ comparisons and swaps.
Space complexity: \$O(1)\$ – sorting is performed in‑place.
Stability: stable (equal elements retain their original relative order).
When to use
Insertion sort is efficient for small data sets or nearly sorted arrays, and it is often used as the final stage of more complex algorithms (e.g., introsort).
Suggested diagram: Flowchart of the insertion sort process.
Bubble Sort
Bubble sort repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. Each pass “bubbles” the largest unsorted element to its correct position at the end of the list.
Algorithm description
Set a flag swapped to true.
While swapped is true:
Set swapped = false.
Traverse the array from index 0 to n‑i‑2 (where i is the current pass number).
If the current element is greater than the next element, swap them and set swapped = true.
When a complete pass makes no swaps, the array is sorted.
Pseudocode
do
swapped = false
for i = 0 to n‑2
if A[i] > A[i+1]
swap A[i] and A[i+1]
swapped = true
while swapped
Complexity analysis
Best case (already sorted): \$T_{\text{best}}(n) = \Theta(n)\$ if the algorithm includes the early‑exit flag.
Worst and average case: \$T{\text{worst}}(n) = T{\text{avg}}(n) = \Theta(n^{2})\$ comparisons and swaps.
Space complexity: \$O(1)\$ – in‑place sorting.
Stability: stable, because swaps are only performed on adjacent elements.
When to use
Bubble sort is rarely used in practice due to its poor performance, but it is valuable for teaching basic sorting concepts and for situations where the data set is extremely small and simplicity is paramount.
Suggested diagram: Illustration of elements “bubbling” to the top of the list after each pass.
Comparison of Insertion Sort and Bubble Sort
Aspect
Insertion Sort
Bubble Sort
Typical use‑case
Small or nearly sorted arrays; as a sub‑routine in hybrid algorithms.
Educational examples; very small data sets.
Best‑case time
\$\Theta(n)\$
\$\Theta(n)\$ (with early‑exit)
Average / worst‑case time
\$\Theta(n^{2})\$
\$\Theta(n^{2})\$
Space complexity
\$O(1)\$
\$O(1)\$
Stability
Stable
Stable
Number of swaps (worst case)
~\$\frac{n^{2}}{4}\$
~\$\frac{n^{2}}{2}\$
Key take‑aways
Both algorithms have \$O(n^{2})\$ worst‑case performance, but insertion sort generally performs fewer swaps.
Insertion sort adapts well to partially sorted data, making it more practical for real‑world small inputs.
Bubble sort’s simplicity makes it a good introductory example, though it is rarely chosen for production code.
Understanding these basic sorts provides a foundation for analysing more advanced algorithms such as merge sort and quicksort.