Пузырьковая сортировка и сортировка вставками
Пузырьковая сортировка - это алгоритм сортировки, который работает путем многократного прохождения списка для сортировки при сравнении пар соседних элементов. Если пара элементов находится в неправильном порядке, они меняются местами, чтобы разместить их в правильном порядке. Этот обход повторяется до тех пор, пока не перестанут требоваться дальнейшие перестановки. Сортировка вставками также является алгоритмом сортировки, который работает путем вставки элемента входного списка в правильную позицию в уже отсортированном списке. Этот процесс повторяется до тех пор, пока список не будет отсортирован.
Что такое пузырьковая сортировка?
Пузырьковая сортировка - это алгоритм сортировки, который работает путем многократного прохождения списка для сортировки при сравнении пар соседних элементов. Если пара элементов находится в неправильном порядке, они меняются местами, чтобы разместить их в правильном порядке. Этот обход повторяется до тех пор, пока не потребуются дальнейшие замены (что означает, что список отсортирован). Поскольку меньшие элементы в списке оказываются наверху, когда пузырь выходит на поверхность, сортировка называется пузырьковой сортировкой. Пузырьковая сортировка - это очень простой алгоритм сортировки, но его средняя временная сложность составляет O(n2) при сортировке списка из n элементов. Из-за этого пузырьковая сортировка не подходит для сортировки списков с большим количеством элементов. Но из-за своей простоты пузырьковая сортировка изучается во время введения в алгоритмы.
Что такое сортировка вставками?
Сортировка вставками - это еще один алгоритм сортировки, который работает путем вставки элемента входного списка в правильную позицию в списке (который уже отсортирован). Этот процесс повторяется до тех пор, пока список не будет отсортирован. При сортировке вставками сортировка выполняется на месте. Следовательно, после i-й итерации алгоритма первые i+1 записи в списке будут отсортированы, а остальная часть списка не отсортирована. На каждой итерации будет браться первый элемент в несортированной части списка и вставляться в нужное место в отсортированном разделе списка. Сортировка вставками имеет среднюю временную сложность O(n2). Из-за этого сортировка вставками также не подходит для сортировки больших списков.
В чем разница между сортировкой пузырьком и сортировкой вставками?
Несмотря на то, что и алгоритмы пузырьковой сортировки, и алгоритмы сортировки вставками имеют среднее время сложности O(n2), пузырьковая сортировка почти всегда уступает сортировке вставками. Это связано с количеством свопов, необходимых для двух алгоритмов (для пузырьковой сортировки требуется больше свопов). Но из-за простоты пузырьковой сортировки размер ее кода очень мал. Также существует вариант сортировки вставками, называемый сортировкой оболочки, который имеет временную сложность O(n3/2), что позволяет использовать его на практике. Кроме того, сортировка вставками очень эффективна для сортировки «почти отсортированных» списков по сравнению с пузырьковой сортировкой.
