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

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

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

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

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

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

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

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

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

После 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.

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

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

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

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

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

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

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

У меня такое ощущение, что это будет быстрее, чем другие обычные 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)только. Другое преимущество заключается в том, что вам не нужны буферы для хранения значений, вы сортируете их в конечном месте назначения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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