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

Question

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

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

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

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

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

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

891 11

algorithm sorting

11 ответов:

Comments

Ничего не найдено.

sasha.sochka · Accepted Answer · 2013-06-24 11:20:16

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

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

tom · Accepted Answer · 2017-04-24 19:57:13

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

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

в каждой итерации следующий элемент прогоняется через отсортированный раздел, пока он не достигнет нужного места:
sorted  | unsorted
1 3 5 8 | 4 6 7 9 2
1 3 4 5 8 | 6 7 9 2
4 пузырится в сортированный раздел

псевдокод:
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])
обратите внимание, что типичные реализации завершаются рано, если во время одной из итераций внешнего цикла не выполняются свопы (поскольку это означает, что массив сортированный.)

разница

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

user5269260 · Accepted Answer · 2015-08-26 18:24:04

еще одно отличие, я не вижу здесь:

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

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

Это также делает гораздо меньше назначений значений.

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

надеюсь, я выразился понятно, если нет, извините, я не уроженец Британии

Joe Tam · Accepted Answer · 2014-08-09 18:39:05

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

jnovacho · Accepted Answer · 2017-08-28 10:20:31

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

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

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

Rajat Paliwal · Accepted Answer · 2014-06-26 13:54:11

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

Aravind · Accepted Answer · 2013-06-24 11:25:03

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

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

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

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

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

DChen · Accepted Answer · 2016-07-26 08:28:41

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

shuva · Accepted Answer · 2017-12-18 00:34:50

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

вставки-вроде так.не более 1 своп в каждой итерации.

Bubble-sort делает от 0 до n свопов в каждой итерации.

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

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

при оптимизации Bubble-sort не получает доступ к тому, что уже есть сортированный.

или нет

вставка-сорт онлайн. Это означает, что вставка-сортировка занимает по одному входу за раз прежде чем он ставит в соответствующее положение. Он не должен сравнивать только adjacent-inputs.

пузырь-вроде не онлайн. Он не работает по одному входу за раз. Он обрабатывает группу входных данных(если не все) в каждой итерации. Пузырь-сортировка только сравнить и поменять adjacent-inputs на каждой итерации.

abhishek agrawal · Accepted Answer · 2018-09-02 21:01:31

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

1.In замена сортировки вставки не требуется.

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

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

4.пример: вставьте книги в библиотеку, расположите карточки.

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

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

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

UmNyobe · Accepted Answer · 2013-06-24 11:39:24

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

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