AdvancedData Structures & Algorithms · Lesson 16 of 20 · Updated ·
Sorting Basics — Bubble, Selection and Insertion Sort
Sorting means putting items in order — marks from highest to lowest, names A to Z. Real programs use the built-in sort, but interviews ask you to write a sort and to explain how it behaves. Three simple algorithms come up again and again: bubble, selection and insertion sort. All three take O(n²) time, but they behave differently, and the differences are what interviewers test.
1. Bubble sort: swap neighbours that are in the wrong order
Walk through the array and compare each pair of neighbours. If the left one is bigger, swap them. After one full pass, the largest value has "bubbled" to the end. Repeat for the rest of the array.
The useful trick: if a whole pass makes no swap, the array is already sorted and you can stop. That makes bubble sort O(n) on an array that is already sorted.
def bubble_sort(a):
n = len(a)
for p in range(n - 1):
swapped = False
for i in range(n - 1 - p): # the last p items are already in place
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
swapped = True
if not swapped:
break
return a
print(bubble_sort([5, 1, 4, 2, 8]))
print(bubble_sort([3, 3, 1]))
[1, 2, 4, 5, 8]
[1, 3, 3]
2. Selection sort: pick the smallest, put it in front
For each position i, find the smallest value in the unsorted part and swap it into position i. It always does the same number of comparisons, so it is O(n²) even on sorted input. Its one strength: it makes at most n − 1 swaps, which matters only when writing to memory is very expensive.
def selection_sort(a):
n = len(a)
for i in range(n - 1):
m = i
for k in range(i + 1, n):
if a[k] < a[m]:
m = k
a[i], a[m] = a[m], a[i]
return a
print(selection_sort([29, 10, 14, 37, 13]))
[10, 13, 14, 29, 37]
Selection sort is not stable: the long-distance swap can jump an item over an equal one. (Stability is explained in the counting sort lesson; in short, a stable sort never changes the order of equal items.)
3. Insertion sort: like sorting cards in your hand
Keep the left part sorted. Take the next item (the "key"), shift every bigger item one step right, and drop the key into the gap.
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
k = i - 1
while k >= 0 and a[k] > key: # shift bigger items right
a[k + 1] = a[k]
k -= 1
a[k + 1] = key
return a
print(insertion_sort([7, 3, 5, 1]))
print(insertion_sort([1, 2, 3, 5, 4]))
[1, 3, 5, 7]
[1, 2, 3, 4, 5]
On a nearly sorted array the inner while loop stops almost at once, so insertion sort runs in close to O(n). That is why real libraries use insertion sort for small pieces: Python's built-in sort (Timsort) and Java's sort for objects both switch to insertion sort on short runs.
The same in Java
import java.util.Arrays;
public class Main {
static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i], k = i - 1;
while (k >= 0 && a[k] > key) {
a[k + 1] = a[k];
k--;
}
a[k + 1] = key;
}
}
public static void main(String[] args) {
int[] a = {7, 3, 5, 1};
insertionSort(a);
System.out.println(Arrays.toString(a));
}
}
[1, 3, 5, 7]
4. Compare them
- All three sort in place: O(1) extra memory.
- For 10⁵ items, n² is 10¹⁰ steps — far too slow. Use an O(n log n) sort (next lesson) or the built-in sort.
- In an interview, if you're allowed to, just call
sorted()/Arrays.sort()and say its complexity: O(n log n).
5. Interview questions about simple sorts
- "Which sort is best for an almost sorted array?" Insertion sort — close to O(n).
- "Which is stable?" Bubble and insertion. Selection is not.
- "Which makes the fewest swaps?" Selection sort: at most n − 1.
- "How do you sort in descending order?" Flip the comparison (
a[k] < keyin insertion sort).
Common mistakes
- Running the inner loop of bubble sort to
n − 1every time instead ofn − 1 − p— correct, but wasted work. - In insertion sort, writing
a[k] >= keyin thewhile— it still sorts, but moves equal items past each other, so the sort is no longer stable. - Forgetting the
swappedcheck, which makes bubble sort O(n²) even on sorted input.
Quick recap
- Bubble: swap neighbours; stop early when a pass makes no swap.
- Selection: pick the minimum each round; few swaps, not stable, always O(n²).
- Insertion: insert each item into the sorted left part; stable and fast on nearly sorted data.
- All three are O(n²) in the worst case and use O(1) extra space.