🔴 Advanced · Lesson 42

Sorting Algorithms

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.

C Language

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.

C Language

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.

C Language

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
    }
}

💡 Great for nearly-sorted data

If the array is already almost in order, insertion sort barely moves anything and finishes very fast.

Comparing the three

Algorithm	Idea	Worst case	Best for
Bubble	Swap neighbours repeatedly	O(n²)	Learning the concept
Selection	Pick the smallest each round	O(n²)	Fewest swaps
Insertion	Insert into sorted part	O(n²)	Nearly-sorted data

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.

🏋️ Practice

Add a line inside each algorithm to print the array after every pass, and sort {5, 2, 4, 1, 3} with all three. Watching each pass makes the differences between them clear.

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.

Frequently Asked Questions

What is sorting in C?

Sorting means arranging the elements of an array into order, usually ascending (smallest to largest). C does not sort for you automatically, so you write an algorithm such as bubble, selection or insertion sort — or use the built-in qsort — to rearrange the array in place.

What is bubble sort and how does it work?

Bubble sort repeatedly walks through the array comparing each pair of neighbours and swapping them if they are in the wrong order. After each full pass the largest remaining value "bubbles" to the end. It keeps passing until no swaps are needed, meaning the array is sorted.

Which sorting algorithm is best for beginners?

Bubble, selection and insertion sort are the classic beginner algorithms because they are short and easy to trace by hand. Insertion sort is often the most practical of the three for small arrays, while bubble sort is the simplest to understand first.

What is the time complexity of bubble, selection and insertion sort?

All three have a worst-case time complexity of O(n²), meaning the work grows with the square of the number of elements. They are fine for small arrays but slow for large ones, where faster O(n log n) methods like quicksort or mergesort are preferred.

What is the difference between selection and insertion sort?

Selection sort repeatedly finds the smallest remaining element and places it next, so it makes few swaps but always scans the rest. Insertion sort takes each element and slides it back into its correct place among the already-sorted part, which is efficient when the data is nearly sorted.

← Back to C Tutorial