Articles / DSA · Part 12

Bubble Sort, Selection Sort, and Insertion Sort

Learn how Bubble Sort, Selection Sort, and Insertion Sort work through step-by-step examples, C programs, and comparisons of their time complexity.

Bubble Sort, Selection Sort, and Insertion Sort

In the previous article, we learned how searching algorithms find elements in an array.

Now let’s understand sorting: arranging elements in a particular order, such as ascending (smallest to largest) or descending (largest to smallest).

Consider this array:

int numbers[] = {5, 3, 8, 1, 2};

After sorting in ascending order:

1 → 2 → 3 → 5 → 8

There are several ways to sort an array. Let’s understand three basic sorting algorithms.

1. Bubble Sort

Bubble Sort repeatedly compares two adjacent elements and swaps them if they are in the wrong order.

After each complete pass, the largest element in the unsorted portion moves to the end.

Example:

Consider:

5    3    8    1    2

Pass 1: Compare adjacent elements and swap when necessary.

Step 1: Compare 5 and 3.

Since 5 is greater than 3, exchange their positions.

Before:  [5]  [3]   8    1    2
After:   [3]  [5]   8    1    2

Step 2: Compare 5 and 8.

Since 5 is smaller than 8, they are already in the correct order. No swapping is needed.

3   [5]  [8]   1    2

Step 3: Compare 8 and 1.

Since 8 is greater than 1, exchange their positions.

Before:  3    5   [8]  [1]   2
After:   3    5   [1]  [8]   2

Step 4: Compare 8 and 2.

Since 8 is greater than 2, exchange their positions.

Before:  3    5    1   [8]  [2]
After:   3    5    1   [2]  [8]

After the first pass:

3    5    1    2    8

The largest element, 8, has reached its correct position.

Pass 2: Repeat the process, ignoring the last sorted element.

Step 1: Compare 3 and 5.

No swapping is needed because 3 is smaller than 5.

[3]  [5]   1    2    8

Step 2: Compare 5 and 1.

Since 5 is greater than 1, exchange their positions.

Before:  3   [5]  [1]   2    8
After:   3   [1]  [5]   2    8

Step 3: Compare 5 and 2.

Since 5 is greater than 2, exchange their positions.

Before:  3    1   [5]  [2]   8
After:   3    1   [2]  [5]   8

After the second pass:

3    1    2    5    8

Continue until the array is sorted:

1    2    3    5    8

C Implementation:

#include <stdio.h>

int main() {
    int a[] = {5, 3, 8, 1, 2};
    int n = 5;

    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;

        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;

                swapped = 1;
            }
        }

        if (swapped == 0)
            break;
    }

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Output:

1 2 3 5 8

The swapped variable helps the algorithm stop early if no elements need to be exchanged.

2. Selection Sort

Selection Sort works by repeatedly finding the smallest element from the unsorted portion of the array and placing it at the beginning of that portion.

Let’s use the same array:

5    3    8    1    2

Pass 1: Find the smallest element in the entire array.

The smallest element is 1. We need to exchange it with the first element, 5.

Before:  [5]   3    8   [1]   2
After:   [1]   3    8   [5]   2

Now, 1 is in its correct position.

Pass 2: Find the smallest element in the remaining unsorted portion.

We ignore the first element because it is already in its correct position.

1  |  3    8    5    2
     └── Unsorted portion ──┘

The smallest element in this portion is 2. Exchange it with 3.

Before:  1   [3]   8    5   [2]
After:   1   [2]   8    5    3

Pass 3: Find the smallest element among 8, 5, and 3.

The smallest is 3. Exchange it with 8.

Before:  1    2   [8]   5   [3]
After:   1    2   [3]   5    8

The array is now sorted:

1    2    3    5    8

C Implementation:

#include <stdio.h>

int main() {
    int a[] = {5, 3, 8, 1, 2};
    int n = 5;

    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;

        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }

        int temp = a[i];
        a[i] = a[minIndex];
        a[minIndex] = temp;
    }

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Output:

1 2 3 5 8

Unlike Bubble Sort, Selection Sort finds the smallest element first and then places it in its correct position.

3. Insertion Sort

Insertion Sort works similarly to arranging playing cards in your hand.

You take one card at a time and place it in the correct position among the cards you have already arranged.

The same idea is used to sort an array.

Consider:

5    3    8    1    2

Initially, we consider the first element, 5, as sorted.

Pass 1: Take 3 and compare it with 5.

Since 3 is smaller, move 5 one position to the right and insert 3 before it.

Before:  [5]  [3]   8    1    2

After:    3    5    8    1    2

Pass 2: Take 8.

It is already greater than 5, so it stays in its position.

3    5   [8]   1    2

No movement is needed.

Pass 3: Take 1.

Move the larger elements (8, 5, and 3) one position to the right to make space for 1.

Before:   3    5    8   [1]   2

Move 8:   3    5    _    8    2

Move 5:   3    _    5    8    2

Move 3:   _    3    5    8    2

Insert 1:  1    3    5    8    2

Pass 4: Take 2.

Move the larger elements (8, 5, and 3) one position to the right and insert 2 in the empty position.

Before:   1    3    5    8   [2]

Move 8:   1    3    5    _    8

Move 5:   1    3    _    5    8

Move 3:   1    _    3    5    8

Insert 2:  1    2    3    5    8

The array is now sorted.

C Implementation:

#include <stdio.h>

int main() {
    int a[] = {5, 3, 8, 1, 2};
    int n = 5;

    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;

        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }

        a[j + 1] = key;
    }

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Output:

1 2 3 5 8

Notice that Insertion Sort shifts larger elements to make space for the current element instead of repeatedly swapping adjacent elements.

4. Comparison of the Three Algorithms

All three algorithms arrange elements in order, but their methods are different.

Feature Bubble Sort Selection Sort Insertion Sort
Main idea Compare adjacent elements and swap Find the smallest element Insert each element into its correct position
Best-case time O(n) O(n²) O(n)
Average-case time O(n²) O(n²) O(n²)
Worst-case time O(n²) O(n²) O(n²)
Extra space O(1) O(1) O(1)
Best suited for Learning basic sorting Situations where fewer swaps are preferred Small or nearly sorted arrays

Note: The best-case O(n) for Bubble Sort assumes the implementation includes the early-stop check shown above.

5. When Should We Use Them?

  • Bubble Sort: Useful for understanding sorting and for very small datasets, but generally inefficient for larger ones.
  • Selection Sort: Useful when we want to minimise the number of swaps.
  • Insertion Sort: Particularly useful for small or nearly sorted datasets.

These algorithms are important for understanding how sorting works, even though more efficient algorithms are commonly used for larger datasets.

Bubble Sort compares adjacent elements, Selection Sort repeatedly selects the smallest element, and Insertion Sort places each element in its correct position.

All three have a worst-case time complexity of O(n²), but their approaches and behaviour differ.

In the next article, we’ll explore Merge Sort and Quick Sort, which use different strategies to sort larger datasets more efficiently.


Further reading: GeeksforGeeks – Comparison of Sorting Algorithms · NCERT – Computer Science, Sorting

Keep a copy

Read offline as a printout or PDF.

farhanpaal.com

Keep reading

DSA · Part 5

Arrays: Understanding the Basics

Learn the basics of arrays, including indexing, memory representation, accessing, updating, traversing, insertion, and deletion with simple C examples.

4 min read

Ask Farhan

Ask anything about Farhan