SyntaxPilot
Courses/DSA and Coding Problems/Lesson 16
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 16 of 90

Sorting 1: bubble, selection, insertion sort

queued

These are the notes for DSA episode 16, the first episode of the sorting block (every binary search problem in episodes 12 to 15 needed sorted data). We build the three simple sorts everyone invents on their own: bubble sort (swap neighbours), selection sort (pick the smallest) and insertion sort (slot each value in, like playing cards). All three are correct, and all three are O(n²): two lakh random numbers time out. But insertion sort is adaptive: on ten lakh nearly sorted numbers it takes milliseconds. We also meet stability. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

Morning assembly: the PT teacher wants a class of forty students in one line, shortest at the front. Nobody learned sorting, but everyone knows three ways to do it:

In the school line As an algorithm
Any two neighbours compare; the taller one steps back. Repeat until nobody swaps. Bubble sort: compare a[j], a[j + 1], swap if out of order
The teacher picks the shortest and calls them to the front, then the shortest of the rest, ... Selection sort: find the minimum, put it at position i
Students arrive one by one; each walks in from the back and stops behind someone shorter. Like sorting playing cards in your hand. Insertion sort: shift bigger values right, drop the new value in

Problem statement

Rearrange an array of integers into non-decreasing order: [5, 1, 4, 2, 8] → [1, 2, 4, 5, 8].

  • In-place: sort inside the same array using O(1) extra space (a few variables).
  • We compare sorts by counting comparisons and swaps (or shifts).
  • Edge cases to test: an empty array, duplicates ([3, 3, 1, 3]), already sorted input.

Bubble sort: swap neighbours

Walk left to right comparing each pair of neighbours; swap if the left one is bigger. After pass 1 the largest value has been carried ("bubbled") all the way to the end, so each pass can stop one place earlier. If a whole pass makes no swaps, the array is sorted: stop early.

Pass Swaps Array after the pass
start [5, 1, 4, 2, 8]
1 5↔1, 5↔4, 5↔2 (5 < 8: no swap) [1, 4, 2, 5, 8]
2 4↔2 [1, 2, 4, 5, 8]
3 none → swapped = false → break [1, 2, 4, 5, 8]
import java.util.*;

public class Main {
    static void bubble(int[] a) {
        int n = a.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - 1 - i; j++)
                if (a[j] > a[j + 1]) {
                    int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                    swapped = true;
                }
            if (!swapped) break;
        }
    }
    public static void main(String[] args) {
        int[] a = {5, 1, 4, 2, 8};
        bubble(a);
        System.out.println(Arrays.toString(a));
        int[] e = {};
        bubble(e);
        System.out.println(Arrays.toString(e));
        int[] d = {3, 3, 1, 3};
        bubble(d);
        System.out.println(Arrays.toString(d));
    }
}

Output:

[1, 2, 4, 5, 8]
[]
[1, 3, 3, 3]

The inner loop stops at n - 1 - i: after i passes the last i values are final, and the loop reads a[j + 1], so it must stop one early.

Selection sort: pick the smallest

For each position i, scan the rest of the array for the minimum and swap it into position i. That value is now final and never moves again.

i Scan finds Array after the swap
0 min 1 at index 1 [1, 5, 4, 2, 8]
1 min 2 at index 3 [1, 2, 4, 5, 8]
2, 3 already in place [1, 2, 4, 5, 8]

At most one swap per position (n - 1 in total): useful when moving an item is expensive. But the scan always compares everything: about n²/2 comparisons even on sorted input.

    static void selection(int[] a) {
        int n = a.length;
        for (int i = 0; i < n - 1; i++) {
            int min = i;
            for (int j = i + 1; j < n; j++)
                if (a[j] < a[min]) min = j;
            int t = a[i]; a[i] = a[min]; a[min] = t;
        }
    }

With the same main (calling selection) it printed [1, 2, 4, 5, 8], [], [1, 3, 3, 3].

Insertion sort: like playing cards

The left part a[0..i-1] is always sorted. Take the next value, the key a[i]; shift every bigger value in the sorted part one place right, then drop the key into the gap.

Key Shifts Array after
1 5 → right [1, 5, 4, 2, 8]
4 5 → right (1 < 4 stops) [1, 4, 5, 2, 8]
2 5 → right, 4 → right (1 < 2 stops) [1, 2, 4, 5, 8]
8 none: one comparison [1, 2, 4, 5, 8]

A value that is already in place costs one comparison. That is the secret of insertion sort.

    static void insertion(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i], j = i - 1;
            while (j >= 0 && a[j] > key) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = key;
        }
    }

With the same main it printed [1, 2, 4, 5, 8], [], [1, 3, 3, 3].

The same three sorts in C++ and Python

#include <bits/stdc++.h>
using namespace std;

void bubble(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); swapped = true; }
        if (!swapped) break;
    }
}
void selection(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {
        int mn = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[mn]) mn = j;
        swap(a[i], a[mn]);
    }
}
void insertion(vector<int>& a) {
    for (int i = 1; i < (int)a.size(); i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;
    }
}
void show(const vector<int>& a) { for (int x : a) cout << x << " "; cout << "\n"; }
int main() {
    vector<int> a = {5, 1, 4, 2, 8}, b = a, c = a;
    bubble(a); selection(b); insertion(c);
    show(a); show(b); show(c);
}

Output: 1 2 4 5 8 three times.

def bubble(a):
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break

def selection(a):
    n = len(a)
    for i in range(n - 1):
        mn = i
        for j in range(i + 1, n):
            if a[j] < a[mn]:
                mn = j
        a[i], a[mn] = a[mn], a[i]

def insertion(a):
    for i in range(1, len(a)):
        key, j = a[i], i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key

for f in (bubble, selection, insertion):
    a = [5, 1, 4, 2, 8]
    f(a)
    print(f.__name__, a)

Output:

bubble [1, 2, 4, 5, 8]
selection [1, 2, 4, 5, 8]
insertion [1, 2, 4, 5, 8]

Two real out-of-bounds bugs

Bug 1: bubble sort's inner loop one step too far

            for (int j = 0; j < n - i; j++)
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
    at Main.bubble(Main.java:9)

On the first pass j reaches 4 and a[j + 1] is a[5], one past the end. A loop that reads a[j + 1] must stop at n - 1 - i.

Bug 2: insertion sort's condition in the wrong order

            while (a[j] > key && j >= 0) {
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 5
    at Main.insertion(Main.java:7)

When the key is the smallest so far, j walks down to -1 and a[-1] is read before the j >= 0 check. && stops at the first false part (short-circuit evaluation), so put j >= 0 first.

The big input: why all three are O(n²)

Two lakh random numbers:

        int n = 200000;
        int[] a = new int[n];
        Random r = new Random(1);
        for (int i = 0; i < n; i++) a[i] = r.nextInt(1000000);
        long t0 = System.nanoTime();
        bubble(a);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(a[0] + " " + a[n - 1] + "   " + ms + " ms");
  • bubble(a): Time Limit Exceeded
  • insertion(a): Time Limit Exceeded
  • selection(a): Time Limit Exceeded
  • Arrays.sort(a) (for comparison): 1 999988 134 ms
n about n² / 2 comparisons
1,000 5 lakh instant
10,000 5 crore fine
2 lakh 2 × 10¹⁰ minutes

Ten times more numbers means a hundred times more work. The reason is the same for all three: every step does a tiny bit of work. It places one value, or swaps one pair of neighbours, so a value far from home moves one place per swap and may need up to n moves. n values × up to n steps = O(n²). To beat it you need a new idea: split the array, sort the halves, merge (merge sort, next episode). On random data insertion sort does about n²/4 shifts: half of bubble's work, still O(n²).

Nearly sorted? Insertion sort takes milliseconds

Ten lakh numbers, already sorted except that every thousandth pair is swapped (like a register where a few students swapped seats):

        int n = 1000000;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = i;
        for (int i = 0; i + 1 < n; i += 1000) { int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t; }
        long t0 = System.nanoTime();
        insertion(a);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(a[0] + " " + a[n - 1] + "   " + ms + " ms");

Output (timing varies from run to run):

0 999999   28 ms

Five times more numbers than the input that timed out, sorted in milliseconds. Insertion sort costs O(n + number of inversions) (an inversion is a pair i < j with a[i] > a[j]); nearly sorted data has few inversions, so it is close to O(n). This is called adaptive, and it is why real library sorts (Java's TimSort for objects, C++'s introsort) switch to insertion sort for small or nearly sorted pieces.

Stable sorting

The register is in roll-number order: Asha (section B), Ravi (A), Neha (B), Imran (A). The office sorts it by section only. A stable sort keeps students with the same section in their old order (Ravi before Imran, Asha before Neha); an unstable sort may not.

import java.util.*;

public class Main {
    static void selection(String[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++)
                if (a[j].charAt(0) < a[min].charAt(0)) min = j;
            String t = a[i]; a[i] = a[min]; a[min] = t;
        }
    }
    static void insertion(String[] a) {
        for (int i = 1; i < a.length; i++) {
            String key = a[i];
            int j = i - 1;
            while (j >= 0 && a[j].charAt(0) > key.charAt(0)) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = key;
        }
    }
    public static void main(String[] args) {
        String[] s1 = {"B-Asha", "A-Ravi", "B-Neha", "A-Imran"};
        String[] s2 = s1.clone();
        selection(s1);
        insertion(s2);
        System.out.println(Arrays.toString(s1));
        System.out.println(Arrays.toString(s2));
    }
}

Output:

[A-Ravi, A-Imran, B-Neha, B-Asha]
[A-Ravi, A-Imran, B-Asha, B-Neha]

Selection sort is not stable: its first long-distance swap moved B-Asha to index 1, and the second moved her behind B-Neha. Insertion sort is stable: it only moves past strictly bigger keys. Bubble sort is stable too, as long as it swaps only on > (never >=).

Complexity

Sort Best Average Worst Swaps / moves Extra space Stable Adaptive
Bubble (with flag) O(n) O(n²) O(n²) up to n²/2 swaps O(1) yes yes
Selection O(n²) O(n²) O(n²) n - 1 swaps O(1) no no
Insertion O(n) O(n²) O(n²) about n²/4 shifts on random data O(1) yes yes

When to use which: insertion sort for small arrays (a few dozen elements) and nearly sorted data; selection sort when writes are very expensive; bubble sort mostly for teaching. For big random data, use an O(n log n) sort.

Common mistakes

Mistake What you see Why Fix
for (j = 0; j < n - i; j++) ... a[j + 1] ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5 a[j + 1] is past the end j < n - 1 - i
while (a[j] > key && j >= 0) ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 5 a[j] read before the check j >= 0 && a[j] > key
Bubble sort without the swapped flag sorted input still costs n²/2 comparisons no early exit break when a pass swaps nothing
Swapping inside selection's inner loop many swaps; it becomes a slow exchange sort swap only after the scan remember min, swap once
a[j] >= a[j + 1] in bubble sort still sorted, but unstable (equal keys swap) swaps equal values use >
Expecting a simple sort to pass n = 10⁵ Time Limit Exceeded O(n²) an O(n log n) sort

Mini project: the assembly line-up

Read students as name height pairs and print them sorted by height with insertion sort, keeping roll-number order for equal heights (stability). Print the number of shifts it made. Then shuffle only two students and sort again: compare the shift counts and explain the difference with the word "adaptive".

Practice

  1. Sort in descending order with insertion sort.
Solution

Flip one comparison: while (j >= 0 && a[j] < key). For [5, 1, 4, 2, 8] it printed [8, 5, 4, 2, 1].

  1. How many swaps does bubble sort make on [5, 1, 4, 2, 8]?
Solution

4: three in pass 1 (5↔1, 5↔4, 5↔2) and one in pass 2 (4↔2). A counter swaps++ inside the if printed 4. (The number of swaps always equals the number of inversions.)

  1. Make selection sort stable.
Solution

Instead of swapping a[i] and a[min], take a[min] out and shift a[i..min-1] one place right, then put it at i:

            String key = s[min];
            for (int k = min; k > i; k--) s[k] = s[k - 1];
            s[i] = key;

On the register it printed [A-Ravi, A-Imran, B-Asha, B-Neha]. It now does O(n²) moves instead of n - 1 swaps.

  1. Binary insertion sort: find the key's spot with binary search. Does it make insertion sort O(n log n)?
Solution

No. Binary search (an upper bound, to stay stable) cuts comparisons to O(n log n), but the values still have to be shifted one by one, which is O(n²) in the worst case.

Quick quiz

How many passes does bubble sort (with the swapped flag) make on {1, 2, 3, 4, 5}?

  • 1
  • 4
  • 5
  • 0
Answer

1. The first pass compares 4 pairs, swaps nothing, so swapped stays false and the loop breaks: 4 comparisons, the O(n) best case.

Interview questions

  1. Which simple sort would you use for nearly sorted data, and why? Insertion sort: O(n + inversions), close to O(n).
  2. Which one makes the fewest swaps? Selection sort: at most n - 1.
  3. Which are stable? Bubble and insertion (with strict >); selection is not.
  4. What does in-place mean? O(1) extra memory; all three are in-place.
  5. Why are they O(n²)? Each step fixes one value or swaps one neighbour pair; a value far from home needs up to n moves.
  6. What is the best case of bubble sort? O(n) with the early-exit flag, on sorted input; without the flag, O(n²).
  7. Why do library sorts use insertion sort inside? For small pieces (around 16 to 32 elements) its low overhead beats the fast sorts.

Glossary

Term Meaning
Sorting Rearranging values into order, here non-decreasing
Comparison Checking which of two values is bigger
Swap Exchanging two values, using a temporary variable t
Shift Moving a value one place right to make room
Pass One full walk through (part of) the array
Bubble sort Repeatedly swapping out-of-order neighbours; the biggest value "bubbles" to the end each pass
Selection sort Repeatedly selecting the minimum of the unsorted part and swapping it into place
Insertion sort Inserting each new value into the sorted part on its left
Key The value being inserted in insertion sort
In-place Uses O(1) extra memory
Stable Equal keys keep their original relative order
Adaptive Runs faster when the input is already nearly sorted
Inversion A pair i < j with a[i] > a[j]; a sorted array has none
O(n²) Work grows with the square of n: 10× the data, 100× the time
Short-circuit evaluation && stops at the first false part, so later parts are not evaluated
ArrayIndexOutOfBoundsException Java's runtime error for an index outside 0..length-1
Time Limit Exceeded (TLE) Too slow for the judge's limit (8 s in the SyntaxPilot compiler)

Summary

  • Bubble sort swaps neighbours and stops when a pass swaps nothing; selection sort picks the minimum (n - 1 swaps); insertion sort shifts bigger values right and drops the key in.
  • Loop bounds: j < n - 1 - i when reading a[j + 1]; j >= 0 && a[j] > key in that order.
  • All three are O(n²) on random data: two lakh numbers time out.
  • Insertion sort is adaptive (near O(n) on nearly sorted data) and stable; selection sort is not stable.
  • All three are in-place with O(1) extra space.

Next episode: Merge sort and counting inversions.