Разница между пузырьковой сортировкой и вставкой сортировки

Сортировка пузырьков и сортировка вставок

Пузырьковая сортировка - это алгоритм сортировки, который работает по списку, который должен быть отсортирован повторно при сравнении пар соседних элементов. Если пара элементов находится в неправильном порядке, они меняются местами, чтобы расположить их в правильном порядке. Этот обход повторяется до тех пор, пока дальнейшие перестановки не требуются. Вставка сортировки также является алгоритмом сортировки, который работает путем вставки элемента в список ввода в правильную позицию в списке, который уже отсортирован. Этот процесс применяется несколько раз, пока список не будет отсортирован.

Что такое пузырьковая сортировка?

Пузырьковая сортировка - это алгоритм сортировки, который работает по списку, который должен быть отсортирован повторно при сравнении пар соседних элементов. Если пара элементов находится в неправильном порядке, они меняются местами, чтобы расположить их в правильном порядке. Этот обход повторяется до тех пор, пока дальнейшие перестановки не требуются (что означает, что список отсортирован). Поскольку более мелкие элементы в списке достигают вершины, когда пузырь выходит на поверхность, ему присваивается название сортировки по пузырькам. Bubble sort - очень простой алгоритм сортировки, но он имеет среднюю сложность по времени O (n2) при сортировке списка с n элементами. Из-за этого пузырьковая сортировка не подходит для сортировки списков с большим количеством элементов. Но из-за своей простоты, пузырьковая сортировка преподается во время введения в алгоритмы.

Что такое вставка сортировки?

Вставка сортировки - это еще один алгоритм сортировки, который работает путем вставки элемента в список ввода в правильную позицию в списке (который уже отсортирован). Этот процесс применяется несколько раз, пока список не будет отсортирован. В сортировке вставки сортировка выполняется на месте. Поэтому после i-й итерации алгоритма первые записи i + 1 в списке будут отсортированы, а остальная часть списка будет отсортирована. На каждой итерации первый элемент в несортированной части списка будет взят и вставлен в правильное место в отсортированном разделе списка. Сортировка вставки имеет среднюю сложность по времени O (n2). Из-за этого вставка сортировки также не подходит для сортировки больших списков.

В чем разница между Bubble Sort и Insertion Sort?

Даже при том, что оба алгоритма сортировки пузырьков и сортировки вставкой имеют среднюю сложность времени O (n2), сортировка пузырьков почти всегда превосходит сортировку вставкой. Это связано с количеством перестановок, необходимых для двух алгоритмов (для пузырьковых сортировок требуется больше перестановок). Но из-за простоты пузырьковой сортировки размер ее кода очень мал. Также существует вариант сортировки вставки, называемый сортировкой оболочки, который имеет временную сложность O (n3 / 2), что позволило бы использовать его практически. Кроме того, сортировка вставками очень эффективна для сортировки «почти отсортированных» списков по сравнению с сортировкой по пузырькам..