Сортировка вставки против алгоритмов сортировки пузырьков

Я пытаюсь понять несколько алгоритмов сортировки, но я изо всех сил стараюсь увидеть разницу в алгоритме сортировки и сортировки в пузырьках.

Я знаю, что оба являются O (n ²), но мне кажется, что сортировка пузырьков просто пузыривает максимальное значение массива в верхней части для каждого прохода, тогда как сортировка вставки просто поглощает самую низкую значение на дне каждого прохода. Разве они не делают то же самое, но в разных направлениях?

Для сортировки вставки число сравнений/потенциальных свопов начинается с нуля и увеличивается каждый раз (то есть 0, 1, 2, 3, 4,..., n), но для сортировки пузырьков такое же поведение происходит, но при конец сортировки (т.е. n, n-1, n-2,... 0), поскольку сортировка пузырьков больше не требуется сравнивать с последними элементами при их сортировке.

При всем этом, однако, кажется консенсусом, что сортировка вставки лучше вообще. Может ли кто-нибудь сказать мне, почему?

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

Ответ 1

В сортировке пузырьков в i-й итерации у вас есть ni-1 внутренних итераций (n ^ 2)/2 total, но при сортировке вставки у вас есть максимальные итерации на i-м шаге, но i/2 в среднем, так как вы можете прежде чем вы найдете правильное положение для текущего элемента. Таким образом, у вас есть (сумма от 0 до n)/2, которая равна (n ^ 2)/4;

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

Ответ 2

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

После я итераций упорядочиваются первые я элементы.

В каждой итерации следующий элемент прокручивается через отсортированную секцию, пока не достигнет правильного места:

sorted  | unsorted
1 3 5 8 | 4 6 7 9 2
1 3 4 5 8 | 6 7 9 2

В сортированную секцию

псевдокод:

for i in 1 to n
    for j in i downto 2
        if array[j - 1] > array[j]
            swap(array[j - 1], array[j])
        else
            break

Сортировка пузырьков

После я итераций последние я элементы являются самыми большими и упорядоченными.

В каждой итерации просеивайте через несортированный раздел, чтобы найти максимум.

unsorted  | biggest
3 1 5 4 2 | 6 7 8 9
1 3 4 2 | 5 6 7 8 9

5 разрывается из несортированной секции

псевдокод:

for i in 1 to n
    for j in 1 to n - i
         if array[j] > array[j + 1]
             swap(array[j], array[j + 1])

Обратите внимание, что типичные реализации заканчиваются раньше, если никакие свопы не выполняются во время одной из итераций внешнего цикла (так как это означает, что массив отсортирован).

Разница

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

Ответ 3

Другое отличие, я не видел здесь:

Сортировка пузырьков имеет 3 присваивания значения для swap: вам сначала нужно создать временную переменную, чтобы сохранить значение, которое вы хотите продвинуть вперед (№1), чем вы должны записать другую переменную swap в место, где вы только что сохранили значение (№ 2), а затем вы необходимо написать временную переменную в месте другого места (№ 3). Вы должны сделать это для каждого места - вы хотите идти вперед - сортировать свою переменную в нужном месте.

С вставкой сортировки вы помещаете переменную во временную переменную, а затем помещаете все переменные перед этим пятном 1 пятно назад, до тех пор, пока вы достигнете правильного места для своей переменной. Это делает привязку 1 на место. В конце вы записываете свою временную переменную в место.

Это делает намного меньше присвоений значений.

Это не самая сильная скорость, но я думаю, что это можно упомянуть.

Надеюсь, я выразил себя понятным, если нет, извините, я не нативная Британия.

Ответ 4

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

У меня такое чувство, что это будет быстрее, чем другие обычные алгоритмы n log(n). Потому что сложность будет n*(n log(n)), например. чтение/сохранение каждого значения из потока (O(n)), а затем сортировку всех значений (O(n log(n))), что приводит к O(n^2 log(n))

Наоборот, с помощью функции Вставка Сортировка O(n) для чтения значений из потока и O(n), чтобы поместить значение в нужное место, таким образом, оно O(n^2). Другим преимуществом является то, что вам не нужны буферы для хранения значений, вы сортируете их в конечном месте назначения.

Ответ 5

Bubble Sort не подключен к сети (он не может сортировать поток входов, не зная, сколько элементов будет), потому что он действительно не отслеживает глобальный максимум отсортированных элементов. Когда элемент вставлен, вам нужно будет начать пузырение с самого начала

Ответ 6

сортировка пузырьков лучше, чем сортировка вставки только тогда, когда кто-то ищет верхние элементы k из большого списка чисел т.е. в сортировке пузырьков после k итераций вы получите верхние k элементов. Однако после k-итераций в сортировке вставки он только гарантирует, что эти k-элементы отсортированы.

Ответ 7

Хотя оба вида - O (N ^ 2). Скрытые константы намного меньше в сортировке Insertion. Скрытые константы относятся к фактическому количеству выполненных примитивных операций.

Когда сортировка вставки имеет лучшее время работы?

Массив почти отсортирован - обратите внимание, что сортировка вставки делает меньше операций в этом случае, чем сортировка пузырьков.
Массив имеет относительно небольшой размер: вставка сортирует, вы перемещаете элементы вокруг, чтобы поместить текущий элемент. Это лучше, чем сортировка пузырьков, если количество элементов немного.

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

Ответ 8

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

Ответ 9

Число свопов на каждой итерации

Вставка-сортировка делает не более 1 swap на каждой итерации.
Bubble-sort выполняет от 0 до n свопов на каждой итерации.

Доступ и изменение отсортированной части

Вставлять-сортировать доступ (и при необходимости изменять) отсортированную часть, чтобы найти правильное положение числа, которое рассматривается.
При оптимизации Bubble-sort не получает доступ к уже отсортированному.

В сети или нет

Вставка-сортировка находится в режиме онлайн. Это означает, что Sorting-sort принимает один вход за раз, прежде чем он вставит нужную позицию. Он не должен сравнивать только adjacent-inputs.
Bubble-sort не является онлайн. Он не использует один вход за раз. Он обрабатывает группу входов (если не всех) на каждой итерации. Bubble-sort сравнивает и заменяет adjacent-inputs на каждой итерации.

Ответ 10

сортировка вставки:

1.В вставке сортировка подкачки не требуется.

2. временная сложность сортировки вставки Ω (n) для наилучшего случая и O (n ^ 2) наихудшего случая.

3. Без комплексов по сравнению с пузырьковой сортировкой.

4. Пример: вставить книги в библиотеку, организовать карты.

пузырьковая сортировка: 1. В пузырьковой сортировке требуется замена.

2. временная сложность пузырьковой сортировки Ω (n) для наилучшего случая и O (n ^ 2) наихудшего случая.

3. более сложный по сравнению с сортировкой вставок.

Ответ 11

Сортировка вставки может быть возобновлена как "Ищите элемент, который должен быть в первом положении (минимум), сделайте некоторое пространство, сдвинув следующие элементы и поместите его в первую позицию. Хорошо. Теперь взгляните на элемент, который должен быть на 2-й...." и т.д.

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