Квадратичные сортировки

Квадратичные сортировки

В статье речь пойдет об одной из квадратичных сортировок. Квадратичной она называется потому что совершает квадрат операций. То есть, если массив состоит из 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

Нет комментариев

Оставить комментарий