Другое существенное различие между ними состоит в том, что пузырьковая сортировка является стабильным алгоритмом, а выборочная сортировка - нестабильным алгоритмом. Алгоритм считается устойчивым для элементов с одинаковым ключом, встречающихся в том же порядке, в котором они находились до сортировки в списке или массиве. Как правило, наиболее стабильные и быстрые алгоритмы используют дополнительную память.
Сравнительная таблица
| Основа для сравнения | Пузырьковая сортировка | Сортировка выбора |
|---|---|---|
| основной | Смежный элемент сравнивается и заменяется | Самый большой элемент выбирается и заменяется последним элементом (в случае возрастания). |
| Наилучшая временная сложность | На) | O (n 2 ) |
| КПД | неэффективный | Улучшенная эффективность по сравнению с пузырьковой сортировкой |
| стабильный | да | нет |
| метод | Обменявшись | выбор |
| скорость | Медленный | Быстро по сравнению с пузырьковой сортировкой |
Определение пузырьковой сортировки
Пузырьковая сортировка - это самый простой итеративный алгоритм, который сравнивает каждый элемент или элемент с элементом рядом с ним и заменяет их при необходимости. Проще говоря, он сравнивает первый и второй элемент списка и меняет его местами, если они не находятся в определенном порядке. Аналогично, второй и третий элементы сравниваются и меняются местами, и это сравнение и замена переходят в конец списка. Количество сравнений в первой итерации равно n-1, где n - количество элементов в массиве. Самый большой элемент будет в n-й позиции после первой итерации. И после каждой итерации число сравнений уменьшается, и на последней итерации выполняется только одно сравнение.
Этот алгоритм является самым медленным алгоритмом сортировки. Сложность в лучшем случае (когда список в порядке) типа Bubble имеет порядок n ( O (n) ), а сложность в худшем случае - O (n2) . В лучшем случае это порядка n, потому что он просто сравнивает элементы и не меняет их местами. Этот метод также требует дополнительного места для хранения временной переменной.
Определение сортировки выбора
Сортировка выбора достигла чуть лучшей производительности и эффективнее, чем алгоритм пузырьковой сортировки. Предположим, мы хотим упорядочить массив в порядке возрастания, после чего он функционирует, найдя самый большой элемент и заменив его последним элементом, и повторяем следующий процесс для подмассивов, пока весь список не будет отсортирован.
Ключевые различия между сортировкой по пузырькам и сортировкой по выбору
- В пузырьковой сортировке каждый элемент и смежный элемент сравниваются и меняются местами, если это необходимо. С другой стороны, сортировка выбора работает путем выбора элемента и замены этого конкретного элемента последним элементом. Выбранный элемент может быть самым большим или самым маленьким в зависимости от порядка, то есть возрастания или убывания.
- В худшем случае сложность одинакова в обоих алгоритмах, т. Е. O (n2), но наилучшая сложность отличается. Пузырьковая сортировка занимает порядка n времени, тогда как выборочная сортировка занимает порядка n2 времени.
- Пузырьковая сортировка является стабильным алгоритмом, в отличие от сортировки по выбору неустойчива
- Алгоритм сортировки выбора является быстрым и эффективным по сравнению с сортировкой пузырьков, которая очень медленная и неэффективная.
Заключение
Алгоритм пузырьковой сортировки считается самым простым и неэффективным алгоритмом, но алгоритм сортировки по выбору эффективен по сравнению с пузырьковой сортировкой. Пузырьковая сортировка также требует дополнительного пространства для хранения временной переменной и требует дополнительных перестановок.
