Basic Sorting Algorithms

Introduction

Given an array

a_1, a_2, \ldots, a_n

of $n$ numbers, the task is to sort the array in non-decreasing order.

Below are three simple classical sorting algorithms.

Bubble Sort

Bubble sort works in several passes over the array.

In each pass, we compare adjacent elements one by one. If they are in the wrong order, we swap them.

After each full pass, at least one element moves to its correct position. Therefore, after $n-1$ passes, the whole array becomes sorted.

Insertion Sort

Insertion sort builds the sorted part of the array from left to right.

At iteration $i$ , we assume that the prefix

a[1 \ldots i]

is already sorted. Then we insert the next element $a_{i+1}$ into its correct position inside this sorted prefix.

Selection Sort

Selection sort also works in $n-1$ iterations.

At iteration $i$ , we find the minimum element in the subarray

a[i \ldots n]

and swap it with $a[i]$ .

After that, the first $i$ elements are in their correct positions.

for (int it = 0; it < n - 1; it++) {
    for (int i = 1; i <= n - 1; i++) {
        if (a[i] > a[i + 1]) {
            swap(a[i], a[i + 1]);
        }
    }
}

for (int i = 1; i <= n - 1; i++) {
    for (int j = i + 1; j > 1; j--) {
        if (a[j - 1] > a[j]) {
            swap(a[j - 1], a[j]);
        } else {
            break;
        }
    }
}

for (int i = 1; i <= n - 1; i++) {
    int min_index = i;
    for (int j = i + 1; j <= n; j++) {
        if (a[j] < a[min_index]) {
            min_index = j;
        }
    }
    swap(a[i], a[min_index]);
}