Вставка сортування проти алгоритмів сортування бульбашок

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

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

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

Хоча все це, здається, існує консенсус про те, що сортування вставки краще в цілому. Чи може хто-небудь сказати мені, чому?

Edit: I'm primarily interested in the differences in how the algorithms work, not so much their efficiency or asymptotic complexity.

54
Це добре задокументовано в іншому місці: див., Наприклад, en.wikipedia.org/wiki/Sorting_algorithm . Дуже безглуздо дублювати тут, і хороша відповідь буде експансивною.
додано Автор Bathsheba, джерело

10 Відповіді

Вставка сортування

Після ітерацій 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

Bubble Sort

Після ієрархів 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])

Зверніть увагу, що типові реалізації закінчуються рано, якщо під час одного з ітерацій зовнішнього циклу не відбувається взаємодії (оскільки це означає, що масив сортується).

Різниця

In Вставка сортування elements are bubbled into the sorted section, while in Bubble Sort the maximums are bubbled out of the unsorted section.

89
додано
Плюс 1 для чіткості, дидактичні значення та для інваріантів основного циклу кожного алгоритму. Шкода, вона не містить чіткого порівняння складності (виражена як функція n ), в будь-якому разі я вважаю це кращою відповіддю, ніж прийнята, тому що з цього я можу дивіться різницю.
додано Автор Honza Zidek, джерело
Я думаю, що це повинна бути найкраща відповідь :)
додано Автор Adelin, джерело
Спасибі, це дуже чітко! Я думаю, головне, що я мав наголосити на тому, що оператор break в Insertion Sort означає, що він може припинити кожну ітерацію рано, тобто коли вона знайшла свою позицію у відсортованому розділі. Розбір міхура вимагає, щоб обмін здійснювався, доки найбільший елемент у несортованому розділі не досягне розсортованого розділу, тому він ніколи не закінчиться рано. Хоча це фантастичний підсумок, так що +1
додано Автор Miguel, джерело
@ Тома, ах, ладно, я тоді погляжу. Велике спасибі
додано Автор Karoly, джерело
Чи можу я запитати, чому ви обмінюєте свій товар у вашому псевдокоду вставки, на кожному кроці? якщо (a [j-1]> a [j]), то a [j] = a [j-1] ELSE якщо (a [j-1] e) ніж a [j] = e; перерва; , де e - елемент повинен бути відсортований. За допомогою цього рішення ви не обмінюєте вже відсортовані елементи, просто копіюючи їх. З нетерпінням чекаю вас пояснення, оскільки я трохи заплутався.
додано Автор Karoly, джерело
@ Каролі, я вибрав мою версію, тому що це простіше. Твій трохи швидше, добре, що ви це вказуєте. Вікіпедія описує обидві версії.
додано Автор tom, джерело

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

Ось чому сортування вставки швидше, ніж сортування бульбашками.

28
додано
Ну, ви можете припустити, що я розумію основи . Що я хотів, це порівняння, і це дійсно непогано. Отже, ідея полягає в тому, що, хоча сортування вставки призводить до того, що i-й елемент знижується, і сортування міхура призводить до його бульбашки, сортування вставки не призводить до падіння до самого дна, це просто призводить до падіння у правильному положенні вже сортований розділ. Таким чином, це робить менше порівнянь/обмінних операцій. Це так?
додано Автор Miguel, джерело
добре, але не пояснює різницю алгоритмів.
додано Автор UmNyobe, джерело
так, але, схоже, OP все ще не вловлює різницю в механізмах
додано Автор UmNyobe, джерело
Так, правильно.
додано Автор sasha.sochka, джерело
Пояснення алгоритму в Інтернеті скрізь, я думаю.
додано Автор sasha.sochka, джерело

Інша різниця, я тут не бачив:

Bubble sort has 3 value assignments per swap: you have to build a temporary variable first to save the value you want to push forward(no.1), than you have to write the other swap-variable into the spot you just saved the value of(no.2) and then you have to write your temporary variable in the spot other spot(no.3). You have to do that for each spot - you want to go forward - to sort your variable to the correct spot.

За допомогою сортування вставки ви поміщаєте свою змінну, щоб сортувати за тимчасовою змінною, а потім поставити всі змінні перед цим місцем 1 місце назад, доки ви досягнете правильного місця для своєї змінної. Це робить 1 призначення значення для кожного місця . В кінці ви пишете свою темпер-змінну на місці.

Це також робить набагато менш цінні призначення.

Це не найсильніша швидкість - перевага, але я думаю, це можна згадати.

Я сподіваюсь, я висловив себе зрозумілим, якщо ні, вибачте, я не натив Англія

13
додано
"а потім поставити всі змінні перед цим місцем 1 місце назад" - і чи не те, що також вимагає навантаження призначень, для переміщення даних? (припускаючи, що дані одночасно зберігаються одночасно, а не пов'язаний список)
додано Автор Mark K Cowan, джерело
@MarkKCowan, так, саме там де сортування вставки робить призначення на "місце", як зазначив вищевказаний користувач. В основному, сортування вставки може бути записано з одним призначенням у внутрішній циклі, тоді як bubblesort має 3 призначення в внутрішньому циклі.
додано Автор JSQuareD, джерело

Основною перевагою вставного сорту є те, що це онлайновий алгоритм. Вам не потрібно мати всі значення при старті. Це може бути корисно при роботі з даними, що надходять з мережі, або деяких датчиків.

I have a feeling, that this would be faster than other conventional n log(n) algorithms. Because the complexity would be n*(n log(n)) e.g. reading/storing each value from stream (O(n)) and then sorting all the values (O(n log(n))) resulting in O(n^2 log(n))

Навпаки, використовуючи Insert Sort, для читання значень з потоку та O (n) потрібні O (n) , щоб поставити значення у правильне місце, таким чином це O (n ^ 2) . Іншою перевагою є те, що вам не потрібні буфери для зберігання значень, ви сортуєте їх у кінцевому пункті призначення.

6
додано
Якщо це нормально, для переміщення даних в порядку, що не є просто скануванням масиву, ви можете упорядкувати на льоту набагато ефективніше. наприклад, вставляйте елементи в бінарне дерево, як тільки ви їх приймаєте. Це дає вам O (n log (n)) загальної роботи, що виконується для сортованого збору на кожному кроці на цьому шляху. (Очікуваний порядок в будь-якому пункті O (m) ). Якщо вам просто потрібен відсортований результат в кінці, але ви хочете перекрити розрахунок сортування з часом передачі даних, купа може бути хорошою. (І працює на місці, як вставка-сортування).
додано Автор Peter Cordes, джерело
У будь-якому випадку, для сортування типу бульбашки сортування та вставки не потрібні розміри проблем, достатньо великі для класу складності O (f (n)) , що має значення для деталей та постійних факторів.
додано Автор Peter Cordes, джерело
Виправлення: Куча не є корисним для цього. Вона виконує більшу частину роботи з сортування, коли ви видаляєте елементи у відсортованому порядку, тому зростає так дешево. Мета полягає в тому, щоб більшу частину роботи було виконано до часу останнього прибуття елемента.
додано Автор Peter Cordes, джерело
У будь-якому випадку, якщо вам потрібно було зберегти сортований масив для вставлень n , то насправді воно зводиться до того, який алгоритм найкраще для сортування майже сортованого масиву, де вгорі є один несортований елемент. Багато алгоритмів сортування O (n log (n)) є O (n) у майже розсортованій справі, тому вам не потрібна сума (M = 1..n, O (M * log (M))) робота. Це буде дійсно O (n ^ 2 log (n)) , але при правильному виборі алгоритму вони будуть загальною роботою O (n ^ 2) . Однак для цього найбільш ефективним є вставка-сортування.
додано Автор Peter Cordes, джерело

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

6
додано

добре сортування міхура краще, ніж сортування вставки, лише коли хтось шукає верхні елементи k з великого списку номерів Тобто у сортуванні міхурів після k ітерацій ви отримаєте верхні елементи k. Однак після k ітерацій у сорту вставки він лише гарантує, що ці k-елементи сортуються.

3
додано

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

Коли сортування вставки має кращий час роботи?

  1. Масив майже розсортований - помітите, що сортування вставки робить у цьому випадку менше операцій, ніж сортування бульбашками.
  2. масив відносно невеликого розміру: сортування вставки, ви переміщаєте елементи навколо, щоб поставити поточний елемент. Це лише краще, ніж сортування бульбашок, якщо кількість елементів незначна.

Зверніть увагу, що сортування вставлення не завжди краще, ніж сортування бульбашками. Щоб отримати найкраще з обох світів, ви можете використовувати сортування вставки, якщо масив має малий розмір, і, можливо, об'єднати сортування (або quicksort) для більших масивів.

1
додано
Якщо кількість елементів не мала, як буде краще вибирати бульбашок? Моє розуміння полягає в тому, незалежно від того, чи пересунете ви IS чи обміняєтеся в BS, буде залежати від того, чи порівнюється елемент (IS) чи менше (BS), а не з # елементів. Будь ласка, виправте мене, якщо це неправильно.
додано Автор Mustafa, джерело

Вставка сортування може бути відновлено як " Знайдіть елемент, який повинен бути на першій позиції (мінімальний), зробити деякий пробіл, перемістивши наступні елементи, і поставити його на перше місце. Добре. Тепер подивіться на елемент, який повинен бути на 2-му .... "і так далі ...

Формат бульбашки працює по-різному, що може бути відновлено як " Поки я знаходжу два сусідніх елементи, які знаходяться в неправильному порядку, я обмінюю їх ".

1
додано
Це допомагає сорту вставки, але ваше пояснення сортування міхура не включає фактичні цикли, тому я не можу їх порівнювати. Я вставлю сортування також ефективно має правило Поки я знаходжу два сусідні елементи, які знаходяться в неправильному порядку, я обмінюю їх , це так, як працює цикли, які різні.
додано Автор Miguel, джерело
О, так, це правда ^
додано Автор Miguel, джерело
Чи не така сортування?
додано Автор harold, джерело

Порожній бульбашок практично непотрібний за будь-яких обставин. У випадках використання, коли сортування вставки може мати забагато swapів, вибір сортування може бути використаний, оскільки він гарантує менше N разів підкачки. Оскільки сортування вибору краще, ніж сортування бульбашок, сортування міхура не має випадків використання.

1
додано

Кількість підказок у кожній ітерації

  • Вставка сортування робить не більше 1 обміну в кожній ітерації .
  • Бульбашкове сортування робить від 0 до n підкачки в кожній ітерації.

Доступ і зміна відсортованої частини

  • Вставка-сортування доступу (і, за необхідності, зміни) відсортованої частини, щоб знайти правильну позицію числа, що розглядається.
  • Коли оптимізовано, Bubble-сортування не має доступу до вже сортованого.

Інтернет чи ні

  • Вставка-сортування в режимі онлайн. Це означає, що Insertion-сортування приймає один вхід за один раз перед тим, як він стане в належному положенні. Не потрібно порівнювати лише суміжні входи .
  • Бульбашковий сорт не-онлайн. Він не працює одночасно з одним входом. Він обробляє групу входів (якщо не всіх) у кожній ітерації. Bubble-sort лише порівнюйте та обмінюйте суміжні входи у кожній ітерації.
0
додано