Рекомендуем, 2020

Выбор редакции

Разница между Bubble Sort и Selection Sort

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

Другое существенное различие между ними состоит в том, что пузырьковая сортировка является стабильным алгоритмом, а выборочная сортировка - нестабильным алгоритмом. Алгоритм считается устойчивым для элементов с одинаковым ключом, встречающихся в том же порядке, в котором они находились до сортировки в списке или массиве. Как правило, наиболее стабильные и быстрые алгоритмы используют дополнительную память.

Сравнительная таблица

Основа для сравненияПузырьковая сортировка
Сортировка выбора
основнойСмежный элемент сравнивается и заменяетсяСамый большой элемент выбирается и заменяется последним элементом (в случае возрастания).
Наилучшая временная сложностьНа)O (n 2 )
КПДнеэффективныйУлучшенная эффективность по сравнению с пузырьковой сортировкой
стабильныйданет
методОбменявшисьвыбор
скоростьМедленныйБыстро по сравнению с пузырьковой сортировкой

Определение пузырьковой сортировки

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

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

Определение сортировки выбора

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

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

Ключевые различия между сортировкой по пузырькам и сортировкой по выбору

  1. В пузырьковой сортировке каждый элемент и смежный элемент сравниваются и меняются местами, если это необходимо. С другой стороны, сортировка выбора работает путем выбора элемента и замены этого конкретного элемента последним элементом. Выбранный элемент может быть самым большим или самым маленьким в зависимости от порядка, то есть возрастания или убывания.
  2. В худшем случае сложность одинакова в обоих алгоритмах, т. Е. O (n2), но наилучшая сложность отличается. Пузырьковая сортировка занимает порядка n времени, тогда как выборочная сортировка занимает порядка n2 времени.
  3. Пузырьковая сортировка является стабильным алгоритмом, в отличие от сортировки по выбору неустойчива
  4. Алгоритм сортировки выбора является быстрым и эффективным по сравнению с сортировкой пузырьков, которая очень медленная и неэффективная.

Заключение

Алгоритм пузырьковой сортировки считается самым простым и неэффективным алгоритмом, но алгоритм сортировки по выбору эффективен по сравнению с пузырьковой сортировкой. Пузырьковая сортировка также требует дополнительного пространства для хранения временной переменной и требует дополнительных перестановок.

Top