Драсте! В этой статье мы галопам по Европам рассмотрим популярнейшие алгоритмы сортировки массивов. Реализовывать будем на C++, потому что он крутой.
Осторожно! Текст перенасыщен словом "свап"!
Начнем с того, что вообще значит отсортировать массив, ну, это значит расставить все его элементы в порядке возрастания\убывания, короче упорядочить.
Ну, что ж, поехали.
Нам понадобится
Измерять время работы
Для этого буду использовать библиотеку chrono из STL C++.
Таким образом все это делается, думаю, разберетесь. У меня, кста, там выше using namespace std;, так что да, а вообще обращаться std::chrono:: нужно.
Все результаты буду заносить в табличку и изучать.
Генерировать случайные числа.
Шаблон
Сортировка выбором
Итак, первая сортировочка. Идея алгоритма заключается в том, чтобы найти минимум в массиве и поменять его местами с первым элементом, а потом повторить этот процесс, но начиная со второй ячейки, ведь в первой и так уже минимальное значение и так далее...
А вообще, последний элемент можно точно не свапать, потому что он по-любому максимальный.
Зависимость времени работы от входных данных:
Можем, заметить, что время работы растет по параболе. Сложность данного алгоритма O(n)
Сортировка пузырьком
Всеми любимая. Работает по принципу: идем по массиву, если находим 2, подряд идущих элемента, причем первый больше второго, меняем их местами. Таким образом, маленькие элементы будут опускаться вниз, а большие вверх.
График (фиолетовый):
Получается, сортировка пузырьком - полная фигня? Не спешите с выводами, этот вариант не оптимизированный.
Дело в том, на каком-то этапе, наш массив уже готов, но мы все пытаемся найти какие-то свапы уже в отсортированном массиве, просто пробегая по массиву много раз, проверяя условие, но не меняя элементы местами.
Так происходит очень часто при пузырьковой сортировке. Мы будем делать делать свап на каждой итерации внутреннего цикла, только если наш массив отсортирован в обратном порядке, в остальных случаях свапов будет меньше. Иными словами, чем более наш массив "не отсортирован", тем больше свапов мы сделаем.
К счастью, мы очень просто можем контролить по ходу сортировки отсортирован ли наш массив. Нам просто надо смотреть, был ли свап: если свапов не было, значит данные отсортированы.
Сортировка пузырьком (оптимизированная)
Графчанский (красный):
Ну, что я вам могу сказать....... :) сортировочная пузыревка - и правда фигня.
Сортировка подсчетом
Суперская сортировка, если диапазон чисел заранее известен.
Вы просто создаете массив, в котором индекс - число, а значение - кол-во чисел равных индексу в массиве. Считаете числа. Ну, а потом да, обрабатываете эту инфу. Если будут числа меньше нуля, придется немного ухищряться... Я покажу, как это работает для чисел от 0 до N, чтобы не усложнять (хотя там не очень-то и сложно).
Время работы (черный):
Ну, тут самая тяжелая операция - выделение памяти. От нее и зависит скорость работы, по большому счету. Тут как повезет. Но работает быстро, как видите. Я тестировал на числах [0; 100000].
Сортировка подсчетом (на Мапе)
На случай, если у вас сложные объекты, ну, или еще какие-то причины, по которым вы не можете заюзать массивы, я по приколу сделал эту штуку, используя map<key, value>.
И тут я заметил, что скриню код с комментом "Bubble sort", пампампам.
Граф (Черный):
Ну, что-то близкое к линейной функции, по идее, это должно работать за O(nlogn).
Сортировка за O(nlogn)
Изначально, я хотел реализовать еще и сортировку слиянием (aka merge sort), но статья получилась какая-то длинная, да и я задолбался немножко все это писать, если честно, так что простите уж.... :)
Поэтому. Перед вами. Результаты. Великой и могучей. std::sort:
Фиолетовый:
Хороший nlogn, отличные результаты.
Вывод
Не пишите свои сортировки, все уже есть в стандартной библиотеке.
Для специфических задач можно использовать сортировку подсчетом, она афигенная.
Всем любви и удачи.
Если хотите подробный разбор сортировки слиянием, пишите комментарии, у меня уже все готово!
P.S
Графики построены в Desmos.