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

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

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

Добавление комментария

Ваше Имя:
Ваш E-Mail:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Вставка исходного кода Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера

Введите два слова, показанных на изображении: