Introduction
Given an array
of numbers, the task is to sort the array in non-decreasing order.
Below are three simple classical sorting algorithms.
Given an array
of numbers, the task is to sort the array in non-decreasing order.
Below are three simple classical sorting algorithms.
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 passes, the whole array becomes sorted.
Insertion sort builds the sorted part of the array from left to right.
At iteration , we assume that the prefix
is already sorted. Then we insert the next element into its correct position inside this sorted prefix.
Selection sort also works in iterations.
At iteration , we find the minimum element in the subarray
and swap it with .
After that, the first 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]);
}