Эффективная сортировка
Сортировка слиянием
Определение:
- Сравнение данных с помощью алгоритма сортировки:
- Весь набор данных делится минимум на две группы.
- Пары значений сравниваются между собой, наименьшее перемещается влево.
- После сортировки внутри всех пар, сравниваются левые значения двух левых пар. Таким образом, создаётся группа из четырёх значений: два наименьшие — слева, наибольшие — справа.
- Процесс повторяется до тех пор, пока не останется только один набор.
Особенности:
- Это один из фундаментальных алгоритмов сортировки.
- Данные делятся на как можно более маленькие наборы, которые потом сравниваются.
Эффективность («О» большое):
- Наилучший вариант сортировки: сортировка слиянием — O(n).
- Средний вариант сортировки: сортировка слиянием — O(n log n).
- Худший вариант сортировки: сортировка слиянием — O(n log n).
Быстрая сортировка
Определение:
- Алгоритм сортировки на основе сравнения.
- Весь набор данных делится пополам путём выбора среднего элемента и перемещения всех, кто меньше него, влево.
- Затем такая же процедура итерационно выполняется с левой частью до тех пор, пока не останутся только два элемента. В результате левая часть окажется отсортированной.
- Затем всё то же самое делается с правой частью.
- Этот алгоритм предпочитают использовать в архитектурах вычислительных систем.
Особенности:
- Хотя «О» большое здесь имеет те же значения (а в ряде случаев — хуже), что и у многих других алгоритмов сортировки, но на практике этот алгоритм зачастую работает быстрее, например, той же сортировки слиянием.
- Данные будут последовательно делиться пополам, пока не будут целиком отсортированы.
Эффективность («О» большое):
- Наилучший вариант сортировки: быстрая сортировка — O(n).
- Средний вариант сортировки: быстрая сортировка — O(n log n).
- Худший вариант сортировки: быстрая сортировка — O(n^2).
Пузырьковая сортировка
Определение:
- Алгоритм сортировки на основе сравнения.
- Итерирует слева направо, сравнивая значения внутри каждой пары и перемещая наименьшее влево.
- Процесс повторяется до тех пор, пока ни одно значение уже не может быть перемещено.
Особенности:
- Алгоритм очень прост в реализации, но наименее эффективен из всех трёх, описанных здесь.
- Сравнив два значения и переместив наименьшее влево, алгоритм переходит на одну позицию вправо.
Эффективность («О» большое):
- Наилучший вариант сортировки: пузырьковая сортировка — O(n).
- Средний вариант сортировки: пузырьковая сортировка — O(n^2).
- Худший вариант сортировки: пузырьковая сортировка — O(n^2).
Сравнение алгоритмов сортировки слиянием и быстрой сортировки
- Быстрая сортировка на практике зачастую эффективнее.
- Сортировка слиянием сразу делит набор данных на наименьшие возможные группы, а затем восстанавливает набор, инкрементально сортируя и укрупняя группы.
- Быстрая сортировка последовательно делит набор по среднему значению, пока он не будет отсортирован рекурсивно.