В статье речь пойдет об одной из квадратичных сортировок. Квадратичной она называется потому что совершает квадрат операций. То есть, если массив состоит из n элементов, то он отсортируется за n * n операций.
Итак, код:
#include <iostream>
using namespace std;
int n;
int a[100];int main() {
freopen(«a.in», «r», stdin);
freopen(«a.out», «w», stdout);cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}for (int i = 0; i < n; i++) {
int m = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[m])
m = j;
}
swap(a[i], a[m]);
}for (int i = 0; i < n; i++) {
cout << a[i] << » «;
}return 0;
}
Что же делает данная программа? После ввода исходного массива, мы выполняем следующий алгоритм: Бежим по всему массиву. На шаге i, из элементов, которые стоят между i-тым и последним элементом включительно, выбираем наименьший. Если он меньше i-того, то меняем их местами, а если нет, то и нет смысла его трогать. Элементы, которые стоят до i-того не рассматриваем, т.к. они уже отсортированы, а значит меньше i-того.
Пример:
Шаг 0: 6 3 1 2 5 4
Шаг 1: 1 3 6 2 5 4
Шаг 2: 1 2 6 3 5 4
Шаг 3: 1 2 3 6 5 4
Шаг 4: 1 2 3 4 6 5
Шаг 5: 1 2 3 4 5 6