Sorting is the process of arranging elements in a collection (list, array) in a specific order — typically ascending (smallest to largest) or descending (largest to smallest). Sorting is fundamental because many algorithms (like binary search) require sorted data, and sorted data is far easier for humans to interpret.
Why Sorting Matters
- Enables efficient searching (binary search requires sorted data).
- Makes data presentation cleaner (alphabetical lists, ranked results).
- Helps in detecting duplicates.
- Facilitates merging of data sets.
Bubble Sort
Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. After each full pass, the largest unsorted element "bubbles" to its correct position at the end.
- 1.Algorithm:
- 2.Repeat (n-1) passes for a list of n elements.
- 3.In each pass, compare list[j] and list[j+1]; swap if list[j] > list[j+1].
- 4.After pass i, the last i elements are in their final sorted positions.
- Time Complexity:
- Best case (already sorted): O(n) — with optimised flag.
- Worst / Average case: O(n2).
Space Complexity: O(1) — in-place sort.
Sort [64, 34, 25, 12, 22]
Pass 1: [34,25,12,22,64] — 64 is in place.
Pass 2: [25,12,22,34,64] — 34 is in place.
Pass 3: [12,22,25,34,64] — sorted.
Selection Sort
Selection sort divides the list into a sorted portion (left) and an unsorted portion (right). In each pass, it finds the MINIMUM element from the unsorted portion and places it at the beginning of the unsorted portion.
Algorithm:
1. For i from 0 to n-2:
a. Find the minimum element in list[i..n-1].
b. Swap it with list[i].
Time Complexity: O(n2) in all cases (always scans full unsorted subarray).
Space Complexity: O(1) — in-place.
Number of swaps: O(n) — at most n-1 swaps, making it efficient when writes/swaps are costly.
Insertion Sort
Insertion sort builds the sorted portion one element at a time. Each new element is "inserted" into its correct position in the already-sorted portion by shifting larger elements right.
Algorithm:
1. For i from 1 to n-1:
a. key = list[i].
b. Move all elements in list[0..i-1] that are greater than key one position to the right.
c. Place key in its correct position.
Time Complexity:
- Best case (sorted): O(n).
- Worst / Average: O(n2).
Space Complexity: O(1) — in-place.
Stable sort: yes — equal elements maintain their relative order.
Comparison of Sorting Algorithms
| Algorithm | Best | Average | Worst | Space | Stable |
|-----------|------|---------|-------|-------|--------|
| Bubble | O(n) | O(n2) | O(n2) | O(1) | Yes |
| Selection | O(n2) | O(n2) | O(n2) | O(1) | No |
| Insertion | O(n) | O(n2) | O(n2) | O(1) | Yes |
Stable sort: preserves the relative order of equal elements.
Common mistakes
- Bubble sort pass count — n elements need at most (n-1) passes, not n.
- Forgetting the optimisation flag — without a "swapped" flag, bubble sort is always O(n2) even on sorted data.
- Selection vs Insertion — selection FINDS the minimum; insertion SHIFTS elements to make room.
- Confusing in-place vs extra-space — all three above are in-place (O(1) extra space).
Summary
Sorting organises data for efficiency. Bubble sort compares adjacent pairs and bubbles the maximum to the end each pass. Selection sort finds the minimum and places it at the front. Insertion sort inserts each element into its correct position. All three have O(n2) average complexity but insertion and bubble can achieve O(n) in the best case. All are in-place algorithms.