Bubble Sort
Definition
Bubble Sort is a straightforward, comparison-based sorting algorithm that repeatedly steps through the list, comparing adjacent elements, and swapping them if they are in the wrong order. The largest element "bubbles" to the top with each pass.
pseudocode
procedure bubbleSort(array):
n = length(array)
for i = 0 to n - 1:
swapped = False
for j = 0 to n - i - 2:
if array[j] > array[j + 1] then
// Swap elements
temp = array[j]
array[j] = array[j + 1]
array[j + 1] = temp
swapped = True
end if
end for
// Optimisation: stop if no swaps
if not swapped then
break
end if
end for
end procedureWorked Example
Bubble Sort Trace: [4, 9, 1, 6, 7]
Pass 1:
• Compare 4, 9: No swap → [4, 9, 1, 6, 7]
• Compare 9, 1: Swap → [4, 1, 9, 6, 7]
• Compare 9, 6: Swap → [4, 1, 6, 9, 7]
• Compare 9, 7: Swap → [4, 1, 6, 7, 9]
• 9 is now in final position
Pass 2:
• Compare 4, 1: Swap → [1, 4, 6, 7, 9]
• Compare 4, 6: No swap
• Compare 6, 7: No swap
• 7 is now in final position. A swap was made, so another pass is needed
Pass 3:
• Compare 1, 4: No swap
• Compare 4, 6: No swap
• No swaps were made in this pass, so the array is sorted and the algorithm stops
The array was already in order after pass 2, but the algorithm cannot know that until it completes a pass without swapping.
Pass 1:
• Compare 4, 9: No swap → [4, 9, 1, 6, 7]
• Compare 9, 1: Swap → [4, 1, 9, 6, 7]
• Compare 9, 6: Swap → [4, 1, 6, 9, 7]
• Compare 9, 7: Swap → [4, 1, 6, 7, 9]
• 9 is now in final position
Pass 2:
• Compare 4, 1: Swap → [1, 4, 6, 7, 9]
• Compare 4, 6: No swap
• Compare 6, 7: No swap
• 7 is now in final position. A swap was made, so another pass is needed
Pass 3:
• Compare 1, 4: No swap
• Compare 4, 6: No swap
• No swaps were made in this pass, so the array is sorted and the algorithm stops
The array was already in order after pass 2, but the algorithm cannot know that until it completes a pass without swapping.
Key Point
Bubble Sort Complexity:
• Best Case: O(n) - array already sorted (with optimisation)
• Worst Case: O(n²) - array in reverse order
• Average Case: O(n²)
Why inefficient for large datasets:
• Quadratic growth makes it very slow for large n
• Many unnecessary comparisons even when nearly sorted
When useful:
• Small datasets
• Nearly sorted data (with optimisation)
• Educational purposes (simple to understand)
• Best Case: O(n) - array already sorted (with optimisation)
• Worst Case: O(n²) - array in reverse order
• Average Case: O(n²)
Why inefficient for large datasets:
• Quadratic growth makes it very slow for large n
• Many unnecessary comparisons even when nearly sorted
When useful:
• Small datasets
• Nearly sorted data (with optimisation)
• Educational purposes (simple to understand)
Insertion Sort
Definition
Insertion Sort builds the final sorted array one item at a time, like sorting playing cards in your hand. It picks elements from the unsorted part and places them in the correct position in the sorted part.
pseudocode
procedure insertionSort(array):
n = length(array)
for i = 1 to n - 1:
key = array[i]
j = i - 1
// Move elements greater than key one position ahead
while j >= 0 AND array[j] > key:
array[j + 1] = array[j]
j = j - 1
end while
array[j + 1] = key
end for
end procedureWorked Example
Insertion Sort Trace: [4, 9, 1, 6, 7]
i = 1 (insert 9):
• Sorted: [4], Unsorted: [9, 1, 6, 7]
• 9 > 4, insert after → [4, 9, 1, 6, 7]
i = 2 (insert 1):
• Sorted: [4, 9], Unsorted: [1, 6, 7]
• 1 < 9, shift 9 right
• 1 < 4, shift 4 right
• Insert 1 at start → [1, 4, 9, 6, 7]
i = 3 (insert 6):
• Sorted: [1, 4, 9], Unsorted: [6, 7]
• 6 < 9, shift 9 right
• 6 > 4, insert after 4 → [1, 4, 6, 9, 7]
i = 4 (insert 7):
• Insert after 6 → [1, 4, 6, 7, 9] ✓
i = 1 (insert 9):
• Sorted: [4], Unsorted: [9, 1, 6, 7]
• 9 > 4, insert after → [4, 9, 1, 6, 7]
i = 2 (insert 1):
• Sorted: [4, 9], Unsorted: [1, 6, 7]
• 1 < 9, shift 9 right
• 1 < 4, shift 4 right
• Insert 1 at start → [1, 4, 9, 6, 7]
i = 3 (insert 6):
• Sorted: [1, 4, 9], Unsorted: [6, 7]
• 6 < 9, shift 9 right
• 6 > 4, insert after 4 → [1, 4, 6, 9, 7]
i = 4 (insert 7):
• Insert after 6 → [1, 4, 6, 7, 9] ✓
Key Point
Insertion Sort Complexity:
• Best Case: O(n) - array already sorted
• Worst Case: O(n²) - array in reverse order
• Average Case: O(n²)
Advantage over Bubble Sort:
• Better for nearly sorted data
• Fewer swaps required
• Simple implementation
• Efficient for small datasets
• Best Case: O(n) - array already sorted
• Worst Case: O(n²) - array in reverse order
• Average Case: O(n²)
Advantage over Bubble Sort:
• Better for nearly sorted data
• Fewer swaps required
• Simple implementation
• Efficient for small datasets
Merge Sort
Definition
Merge Sort is an efficient, stable, divide-and-conquer sorting algorithm. It divides the array into two halves, recursively sorts each half, then merges the sorted halves.
pseudocode
function mergeSort(array):
if length(array) <= 1 then
return array
end if
// DIVIDE
mid = length(array) DIV 2
left = mergeSort(array[0..mid-1])
right = mergeSort(array[mid..end])
// CONQUER (merge)
return merge(left, right)
end function
function merge(left, right):
result = []
while left is not empty AND right is not empty:
if left[0] <= right[0] then
append left[0] to result
remove left[0] from left
else
append right[0] to result
remove right[0] from right
end if
end while
// Add remaining elements
append remaining left to result
append remaining right to result
return result
end functionWorked Example
Merge Sort Trace: [7, 4, 2, 6]
| Phase | Working |
|---|---|
| Divide | [7,4,2,6] → [7,4] + [2,6] → [7]+[4] and [2]+[6] |
| Merge sublists | [7]+[4] → [4,7]; [2]+[6] → [2,6] |
| Final merge | [4,7] + [2,6] → [2,4,6,7] |
Key Point
Merge Sort Complexity:
• Best Case: O(n log n)
• Worst Case: O(n log n)
• Average Case: O(n log n)
• Space: O(n) - requires additional memory
Why preferred for large datasets:
• Guaranteed O(n log n) performance
• Stable sort (maintains relative order)
• Predictable regardless of input
Trade-off: Requires extra memory for merging
• Best Case: O(n log n)
• Worst Case: O(n log n)
• Average Case: O(n log n)
• Space: O(n) - requires additional memory
Why preferred for large datasets:
• Guaranteed O(n log n) performance
• Stable sort (maintains relative order)
• Predictable regardless of input
Trade-off: Requires extra memory for merging
Quick Sort
Definition
Quick Sort is a divide-and-conquer sorting algorithm that selects a pivot element and partitions the array such that elements less than the pivot come before it, and elements greater come after. This process repeats recursively.
pseudocode
function quickSort(array, low, high):
if low < high then
// Partition and get pivot position
pivotIndex = partition(array, low, high)
// Recursively sort sub-arrays
quickSort(array, low, pivotIndex - 1)
quickSort(array, pivotIndex + 1, high)
end if
end function
function partition(array, low, high):
pivot = array[high] // Choose last element as pivot
i = low - 1
for j = low to high - 1:
if array[j] <= pivot then
i = i + 1
swap array[i] and array[j]
end if
end for
swap array[i + 1] and array[high]
return i + 1
end functionWorked Example
Quick Sort Trace: [9, 4, 7, 8, 6, 3, 1, 5, 2]
The pivot is the last item of the part being sorted. After each partition the pivot (in bold) is in its final position, with smaller items to its left and larger items to its right.
How step 1 works: only 1 is less than or equal to the pivot, so it is swapped to the front. The pivot is then swapped with the item after it (the 4 that had moved to the second position), which puts 2 in its final place.
A part with one item, such as [1], [3], [7] or [9], is already sorted, so the recursion stops there.
Final sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9]
The pivot is the last item of the part being sorted. After each partition the pivot (in bold) is in its final position, with smaller items to its left and larger items to its right.
| Step | Part being sorted | Pivot | Whole array after the partition |
|---|---|---|---|
| 1 | [9, 4, 7, 8, 6, 3, 1, 5, 2] | 2 | [1, 2, 7, 8, 6, 3, 9, 5, 4] |
| 2 | [7, 8, 6, 3, 9, 5, 4] | 4 | [1, 2, 3, 4, 6, 7, 9, 5, 8] |
| 3 | [6, 7, 9, 5, 8] | 8 | [1, 2, 3, 4, 6, 7, 5, 8, 9] |
| 4 | [6, 7, 5] | 5 | [1, 2, 3, 4, 5, 7, 6, 8, 9] |
| 5 | [7, 6] | 6 | [1, 2, 3, 4, 5, 6, 7, 8, 9] |
A part with one item, such as [1], [3], [7] or [9], is already sorted, so the recursion stops there.
Final sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Key Point
Quick Sort Complexity:
• Best Case: O(n log n) - balanced partitions
• Worst Case: O(n²) - unbalanced partitions (bad pivot choice)
• Average Case: O(n log n)
• Space: O(log n) - in-place sorting
Pivot choice matters:
• First/last element: Risk of O(n²) for sorted data
• Random element: Usually good
• Median-of-three: Better balance
• Best Case: O(n log n) - balanced partitions
• Worst Case: O(n²) - unbalanced partitions (bad pivot choice)
• Average Case: O(n log n)
• Space: O(log n) - in-place sorting
Pivot choice matters:
• First/last element: Risk of O(n²) for sorted data
• Random element: Usually good
• Median-of-three: Better balance