Основное различие между пузырьковой сортировкой и сортировкой вставками состоит в том, что пузырьковая сортировка выполняет сортировку, проверяя соседние элементы данных и меняя их местами, если они находятся в неправильном порядке, в то время как сортировка вставкой выполняет сортировку, передавая один элемент в частично отсортированный массив за один раз.
Алгоритм — это последовательность шагов для решения задачи. Сортировка — это обычная операция, выполняемая с набором данных. Существуют различные алгоритмы для сортировки набора данных. Два из них — пузырьковая сортировка и сортировка вставками. Более того, эти два алгоритма рассматриваются как простые алгоритмы сортировки.
Содержание
- Что такое пузырьковая сортировка — определение, функциональность
- Что такое сортировка вставками — определение, функциональность
- В чем разница между пузырьковой сортировкой и сортировкой вставками
Ключевые термины
Алгоритм, Пузырьковая сортировка, Сортировка вставками
Что такое пузырьковая сортировка
Пузырьковая сортировка — это самый простой алгоритм сортировки. Алгоритм сортирует элементы, сравнивая соседние пары одновременно.
Рассмотрим следующий пример:
40 30 10 70 50 20 60
В пузырьковой сортировке мы сравниваем соседние элементы.
Во-первых, мы рассмотрим 40 и 30. 30 меньше 40. Итак, мы можем поменять эти два числа.
30 40 10 70 50 20 60
Теперь мы можем рассмотреть 40 и 10. 10 меньше 40. Итак, мы можем поменять местами эти два числа.
30 10 40 70 50 20 60
Теперь мы можем рассмотреть 40 и 70. Поскольку 70 больше 40, нет необходимости менять номера.
Далее мы рассмотрим 70 и 50. 50 меньше 70. Итак, мы можем поменять эти два числа.
30 10 40 50 70 20 60
Затем мы можем рассмотреть 70 и 20. Поскольку 20 меньше 70, мы можем поменять эти два элемента.
30 10 40 50 20 70 60
Теперь мы можем рассмотреть 70 и 60. 60 меньше 70. Поэтому мы должны поменять местами эти два числа.
30 10 40 50 20 60 70
Теперь вы можете видеть, что самый большой элемент в наборе данных теперь находится в конце. Другими словами, в конце первого прохода самый большой элемент уже отсортирован. Поэтому в следующий раз нам не нужно считать 70, так как он уже отсортирован. Нам нужно только проверить остальные шесть элементов.
Более того, мы должны выполнять сравнение двух элементов одновременно. Рассмотрим 30 и 10. 10 меньше 30. Итак, мы поменяем эти два числа.
10 30 40 50 20 60 70
Теперь мы рассмотрим 30 и 40. 40 больше 30. Нет необходимости менять местами числа. Затем мы можем рассмотреть 40 и 50. Поскольку 50 больше 40, нет необходимости менять местами.
Теперь рассмотрим 50 и 20. 20 меньше 50. Итак, мы поменяем эти два числа.
10 30 40 20 50 60 70
Теперь рассмотрим 50 и 60. Нет необходимости менять местами. В конце второго прохода сортируется второй по величине элемент. Другими словами, 60 и 70 теперь отсортированы. Процесс продолжается до сортировки всех элементов.
Что такое сортировка вставками
Алгоритм сортировки вставками сортирует набор данных, передавая по одному элементу за один раз в частично отсортированный массив. Таким образом, этот алгоритм сортировки имеет более низкую трудоёмкость.
Рассмотрим следующий пример:
40 30 10 70 50 20 60
Мы считаем 40 частично отсортированным массивом. Когда мы рассматриваем 30, это меньше, чем 40. Таким образом, мы меняем их. Затем мы рассмотрим 30 и 40 в частично отсортированном массиве.
30 40 10 70 50 20 60
Теперь мы рассмотрим 10. 10 меньше 30. Итак, мы размещаем элементы, как показано ниже.10, 30 и 40 находятся в частично отсортированном массиве.
10 30 40 70 50 20 60
Теперь мы рассмотрим 70. Это больше 40, поэтому нет необходимости в каком-либо движении.10, 30, 40, 70 находятся в частично отсортированном массиве.
Теперь рассмотрим 50. Это меньше 70, но больше 40. Мы можем разместить их в правильном положении. 10,30, 40, 50,70 теперь в частично отсортированном массиве.
10 30 40 50 70 20 60
Теперь рассмотрим 20. Он больше 10, но меньше 20. Мы можем поставить его в правильное положение. 10,20,30,40,50, 70 находятся в частично отсортированном массиве.
10 20 30 40 50 70 60
Рассмотрим 60. Это меньше 70, но больше 50. Мы можем поставить его в правильное положение.
10 20 30 40 50 60 70
Теперь мы видим, что все элементы отсортированы. Здесь количество перестановок в сортировке вставок сведено к минимуму, но количество сравнений все еще велико.
Разница между пузырьковой сортировкой и вставкой сортировки
Определение
Пузырьковая сортировка — это простой алгоритм сортировки, который многократно просматривает список, сравнивая соседние пары и меняя их местами, если они находятся в неправильном порядке. Сортировка вставками, с другой стороны, представляет собой простой алгоритм сортировки, который создает окончательный отсортированный список путем передачи по одному элементу за один раз.
Функциональность
В то время как пузырьковая сортировка проверяет соседние элементы и заменяет их соответствующим образом, сортировка вставкой передает каждый элемент за один раз в частично отсортированный массив.
Количество перестановок
Количество перестановок является важной разницей между сортировкой пузырьков и сортировкой вставок. У сортировки вставок меньше перестановок, чем у пузырьковой.
Скорость
Сортировка вставками в два раза быстрее, чем пузырьковая сортировка.
Сложность
Другое различие между пузырьковой сортировкой и сортировкой вставками заключается в том, что сортировка вставками является более сложной, чем пузырьковая сортировка.
Заключение
Пузырьковая сортировка и сортировка вставками подходят для сортировки небольшого набора данных. Оба метода имеют более низкую эффективность по сравнению с другими продвинутыми алгоритмами сортировки, такими как быстрая сортировка и сортировка слиянием. Основное различие между пузырьковой сортировкой и сортировкой вставками заключается в том, что пузырьковая сортировка выполняет сортировку, проверяя соседние элементы данных и меняя их местами, если они находятся в неправильном порядке, тогда как сортировка вставками выполняет сортировку, передавая один элемент в частично отсортированный массив за один раз.
