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

Основное различие между пузырьковой сортировкой и сортировкой вставками состоит в том, что пузырьковая сортировка выполняет сортировку, проверяя соседние элементы данных и меняя их местами, если они находятся в неправильном порядке, в то время как сортировка вставкой выполняет сортировку, передавая один элемент в частично отсортированный массив за один раз.

Алгоритм — это последовательность шагов для решения задачи. Сортировка — это обычная операция, выполняемая с набором данных. Существуют различные алгоритмы для сортировки набора данных. Два из них — пузырьковая сортировка и сортировка вставками. Более того, эти два алгоритма рассматриваются как простые алгоритмы сортировки.

Содержание

  1. Что такое пузырьковая сортировка — определение, функциональность
  2. Что такое сортировка вставками — определение, функциональность
  3. В чем разница между пузырьковой сортировкой и сортировкой вставками

Ключевые термины

Алгоритм, Пузырьковая сортировка, Сортировка вставками

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

Пузырьковая сортировка — это самый простой алгоритм сортировки. Алгоритм сортирует элементы, сравнивая соседние пары одновременно.

Пузырьковая сортировка
Пузырьковая сортировка

Рассмотрим следующий пример:

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 теперь отсортированы. Процесс продолжается до сортировки всех элементов.

Читайте также:  Разница между JavaScript и jQuery

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

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

Сортировка вставками
Сортировка вставками

Рассмотрим следующий пример:

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

Теперь мы видим, что все элементы отсортированы. Здесь количество перестановок в сортировке вставок сведено к минимуму, но количество сравнений все еще велико.

 

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

Определение

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

Функциональность

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

Количество перестановок

Количество перестановок является важной разницей между сортировкой пузырьков и сортировкой вставок. У сортировки вставок меньше перестановок, чем у пузырьковой.

Скорость

Сортировка вставками в два раза быстрее, чем пузырьковая сортировка.

Сложность

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

Заключение

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

Оставьте комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *