Sorting Programs in C – Bubble, Selection, Insertion

In this lesson: Bubble, selection and insertion sort programs in C with pass-by-pass dry run, complexity table and output. Hindi & English.

What is sorting?

Sorting means putting an array in order — usually smallest to largest. It is one of the most common tasks in programming, and writing a sort by hand teaches loops, comparisons and swapping all at once. Here are the three classic beginner algorithms, each doing the same job a different way.

All three sort the array in place and share the same helper — a swap of two elements.

Bubble sort

Compare each neighbour pair and swap if out of order. The biggest value "bubbles" to the end each pass.

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++)
        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;
            }
}

Dry run on {5, 2, 4} — first pass: compare 5&2 → swap → {2,5,4}; compare 5&4 → swap → {2,4,5}. Sorted.

Selection sort

Find the smallest element in the unsorted part and put it in the next position. Repeat.

void selectionSort(int a[], int n) {
    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;   // find smallest
        int t = a[i]; a[i] = a[min]; a[min] = t;  // place it
    }
}

Each round selects the minimum of what is left and swaps it into place — so it makes at most one swap per round.

Insertion sort

Take each element and slide it back into its correct spot among the already-sorted elements, like sorting playing cards in your hand.

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {   // shift bigger ones right
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;                 // drop key into place
    }
}

Comparing the three

All three are O(n²), fine for small arrays. For large data, faster O(n log n) methods like quicksort are used. To find an item in a sorted array, pair these with binary search.

Common mistakes

• Looping too far and reading past the array (watch n - 1 bounds).
• Swapping without a temporary variable, losing a value.
• In insertion sort, forgetting to place key after the while loop.
• Comparing with < vs > the wrong way, sorting in the wrong direction.

Summary

• Sorting arranges an array in order; C has no automatic sort for you.
• Bubble sort swaps neighbours until no swaps are left.
• Selection sort repeatedly places the smallest remaining element.
• Insertion sort slides each element into the sorted part; great when nearly sorted.
• All three are O(n²) — good for small arrays; use O(n log n) methods for large data.