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

87

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

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

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

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

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

Migwell
источник
1
Это хорошо описано в другом месте: см., Например, en.wikipedia.org/wiki/Sorting_algorithm . Повторять здесь бессмысленно, и хороший ответ будет обширным.
Вирсавия
@Bathsheba 75 человек, проголосовавших "за", и 88 тыс., Просмотревших вопрос, похоже, не согласны; )
парсер
@parsecer: Ха! Теперь мне нужно пересмотреть ответы. Текущий ответ с наибольшим количеством голосов полезен; не уверен насчет других. Вот некоторые очки репутации, потерянные из-за голосования против. Утверждение «Вот почему сортировка вставкой быстрее, чем пузырьковая сортировка» в принятом ответе не обязательно верно.
Вирсавия
@Bathsheba О нет
синтаксический анализатор

Ответы:

41

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

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

саша.сочка
источник
2
Я думаю, что объяснение алгоритмов есть повсюду в сети.
sasha.sochka
4
да, но похоже, что ОП все еще не улавливает разницы в механизмах
UmNyobe
15
Что ж, вы можете предположить, что я понимаю основы . Я хотел сравнения, и это действительно неплохо. Идея состоит в том, что в то время как сортировка вставкой заставляет i-й элемент опускаться вниз, а пузырьковая сортировка заставляет его всплывать вверх, сортировка вставкой не заставляет его опускаться до самого низа, она просто заставляет его опускаться в нужное положение в уже отсортированный раздел. Таким образом, выполняется меньше сравнений / свопов. Это правильно?
Migwell
2
Какая? «Итак, у вас есть (сумма от 0 до n) / 2, что составляет (n ^ 2) / 4 всего» Это требует некоторых пояснений, пожалуйста! 0 + 1 + 2 + 3 + 4 + 5 = 15; 15/2 = 7,5; 7,5 * 4 = 30; sqrt (30) = тарабарщина
Джон Смит
@JohnSmith Я считаю, что в ответе есть небольшая ошибка. Сумма от 1 до n равна n * (n + 1) / 2, так как это треугольное число. Посмотрите на треугольное число, чтобы узнать больше. Таким образом, деленное на 2 будет просто n * (n + 1) / 2.
CognizantApe
124

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

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

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

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

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

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

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

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])

Note that typical implementations terminate early if no swaps are made during one of the iterations of the outer loop (since that means the array is sorted).

Difference

In insertion sort elements are bubbled into the sorted section, while in bubble sort the maximums are bubbled out of the unsorted section.

tom
источник
10
Спасибо, это очень понятно! Я думаю, что главное, что мне нужно было выделить, это то, что оператор break в Insertion Sort означает, что он может завершать каждую итерацию раньше, то есть когда он нашел свою позицию в отсортированном разделе. Сортировка пузырьков требует, чтобы обмен продолжался до тех пор, пока самый большой элемент в несортированном разделе не достигнет отсортированного раздела, поэтому никогда не завершится раньше. Хотя это фантастическое резюме, так что +1
Migwell
4
Я думаю, что это должен быть лучший ответ :)
Аделин
2
Плюс 1 за ясность, дидактическую ценность и инварианты основного цикла каждого алгоритма. Жалко, что он не содержит явного сравнения сложности (выраженной как функция от n ), в любом случае я считаю это лучшим ответом, чем принятый, поскольку отсюда я вижу разницу.
Honza Zidek
Могу я спросить, почему вы меняете местами свой элемент в псевдокоде Insis на каждом этапе? if (a [j-1]> a [j]), то a [j] = a [j-1] ELSE if (a [j-1] <e && a [j]> e), чем a [j] = e; перерыв; , где e - это элемент, который нужно отсортировать. С помощью этого решения вы не меняете местами уже отсортированные элементы, а просто копируете их. С нетерпением жду вашего объяснения, так как я немного запутался.
Karoly
@Karoly, я выбрал свою версию, потому что она проще. У вас чуть быстрее, хорошо, что вы указали. Википедия описывает обе версии.
том
16

Еще одна разница, которую я здесь не заметил:

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

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

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

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

Надеюсь, я выразился понятно, если нет, извините, я не коренной британец

user5269260
источник
1
«а затем поместите все переменные перед этим пятном на 1 пятно назад» - и разве для этого не требуется много назначений для сдвига данных? (при условии, что данные в любом случае хранятся непрерывно, а не в виде связанного списка)
Марк К. Коуэн
@MarkKCowan, да, вот где сортировка вставкой выполняет присваивание на «место», как выразился вышеупомянутый пользователь. По сути, сортировка вставкой может быть записана с одним назначением во внутреннем цикле, в то время как пузырьковая сортировка имеет 3 назначения во внутреннем цикле.
JSQuareD
9

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

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

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

Jnovacho
источник
Если можно, чтобы обход данных по порядку был чем-то другим, кроме простого сканирования массива, вы можете выполнять сортировку на лету гораздо более эффективно. например, вставляйте элементы в двоичное дерево по мере их получения. Это дает вам O(n log(n))общий объем выполненной работы, чтобы иметь отсортированную коллекцию на каждом этапе пути. (Обход по порядку в любой точке есть O(m)). Если вам просто нужен отсортированный результат в конце, но вы хотите перекрыть вычисление сортировки со временем передачи данных, куча может быть хорошей. (И работает на месте, как сортировка вставкой).
Питер Кордес
В любом случае, ни пузырьковая сортировка, ни сортировка вставкой не идеальны для этого, поскольку размеры задач достаточно велики, чтобы O(f(n))класс сложности имел большее значение, чем детали реализации и постоянные факторы.
Питер Кордес
Исправление: куча для этого не годится. Он выполняет большую часть работы по сортировке, поскольку вы удаляете элементы в отсортированном порядке, поэтому выращивание так дешево. Здесь цель состоит в том, чтобы большая часть работы была выполнена к моменту поступления последнего элемента.
Питер Кордес
В любом случае, если вам нужно было поддерживать отсортированный массив для nвставок, то на самом деле все сводится к тому, какой алгоритм лучше всего подходит для сортировки почти отсортированного массива, где есть один несортированный элемент наверху. Многие O(n log(n))алгоритмы сортировки находятся O(n)в почти отсортированном случае, поэтому неправда, что вам понадобится sum(M=1..n, O(M * log(M)) )работа. Это действительно так O(n^2 log(n)), но при правильном выборе алгоритма они станут O(n^2)полной работой. Однако сортировка вставкой является наиболее эффективной для этого.
Питер Кордес
7

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

Джо Тэм
источник
5

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

Раджат Паливал
источник
2

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

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

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

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

Аравинд
источник
2
Если количество элементов невелико, что может быть лучше пузырьковой сортировки? Насколько я понимаю, то, скользите ли вы в IS или меняете местами в BS, будет зависеть от того, больше ли сравниваемый элемент (IS) или меньше (BS), а не от количества элементов. Пожалуйста, поправьте меня, если ошиблись.
Мустафа
1

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

  • Сортировка вставкой выполняет не более 1 обмена за каждую итерацию .
  • Bubble-sort выполняет замену от 0 до n на каждой итерации.

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

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

Онлайн или нет

  • Вставка-сортировка онлайн. Это означает, что сортировка вставкой принимает по одному вводу за раз, прежде чем помещается в соответствующее положение. Необязательно только сравниватьadjacent-inputs .
  • Сортировка пузырьков не онлайн. Он не управляет одним входом за раз. Он обрабатывает группу входов (если не все) на каждой итерации. Пузырьковая сортировка только сравнивает и меняет местамиadjacent-inputs на каждой итерации.
Шува
источник
0

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

DChen
источник
0

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

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

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

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

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

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

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

3. более сложный, чем сортировка вставкой.

абхишек агравал
источник
1
Почему свопинг не требуется? Он меняет местами элементы, чтобы поместить элемент в правильное положение. И я бы не сказал, что пузырьковая сортировка более сложная.
парсер 05
-1

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

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

UmNyobe
источник
Это действительно помогает с сортировкой вставкой, но ваше объяснение пузырьковой сортировки не включает фактические циклы, поэтому я не могу их сравнить. Сортировка вставкой также эффективно имеет правило. Пока я нахожу два соседних элемента, которые находятся в неправильном порядке, я меняю их местами , отличается способ работы циклов.
Migwell
3
Разве это не сортировка выбора?
Harold