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

Сортировка по пузырям и сортировка по выбору

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

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

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

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

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

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

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