[Powered by Google Translate] [Бульбашкового сортування]
[JACKSON Steinkamp HARVARD UNIVERSITY]
[Це CS50. CS50TV]
Bubble Сортування приклад алгоритму сортування -
тобто, порядок сортування набір елементів в
зростанням або за спаданням.
Наприклад, якщо ви хочете відсортувати масив, що складається з чисел
[3, 5, 2, 9], правильне застосування бульбашкового сортування повернеться
упорядкований масив [2, 3, 5, 9] в порядку зростання.
Тепер, я збираюся пояснити, в псевдокоді, як працює алгоритм.
>> Скажімо, ми сортування список з 5 чисел - 3, 2, 9, 6 і 5.
Алгоритм починається, дивлячись на перші два елементи, 3 і 2,
і перевірки, якщо вони вийшли з ладу по відношенню один до одного.
Вони - 3 більше, ніж 2.
Щоб бути в порядку зростання, вони повинні бути навпаки.
Таким чином, ми поміняти їх місцями.
Тепер список виглядає наступним чином: [2, 3, 9, 6, 5].
>> Далі ми подивимося на другий і третій елементи, 3 і 9.
Вони в правильному порядку відносно один одного.
Тобто, 3 менше, ніж 9, так що алгоритм не поміняти їх місцями.
Далі, ми дивимося на 9 і 6. Вони вийшли з ладу.
>> Отже, нам потрібно, щоб поміняти їх місцями, бо 9 більше, ніж 6.
Нарешті, ми подивимося на останні два цілих числа, 9 та 5.
Вони вийшли з ладу, тому вони повинні бути замінені.
Після першого повного проходу по списку,
це виглядає так: [2, 3, 6, 5, 9].
Не погано. Це майже відсортований.
Але нам потрібно запустити через список ще раз, щоб отримати його повністю відсортований.
Два менше, ніж 3, тому ми не поміняти їх місцями.
>> Три становить менше 6, так що ми не поміняти їх місцями.
Шість перевищує 5. Ми помінялися місцями.
Шість менше, ніж 9. Ми не поміняти.
Після другої прохід, вона виглядає наступним чином: [2, 3, 5, 6, 9]. Perfect.
Тепер, давайте запишемо його в псевдокоді.
В принципі, для кожного елемента в списку, ми повинні дивитися на це
і елемент безпосередньо в своєму праві.
Якщо вони не в порядку відносно один одного - тобто, якщо елемент зліва
більше, ніж той, на правому - ми повинні поміняти місцями два елементи.
>> Ми робимо це для кожного елемента списку, і ми зробили один прохід.
Тепер ми просто повинні зробити наскрізний достатню кількість разів, щоб переконатися, що список
повністю, правильно сортуються.
Але скільки разів ми повинні пройти через список
гарантувати, що ми зробили?
Ну, гіршому випадку, якщо ми маємо абсолютно зворотну списку.
Тоді вона приймає ряд пройти прохідні дорівнює числу
елементів N-1.
Якщо це не має сенсу, інтуїтивно, думаю простий випадок - список [2, 1].
>> Це буде взяти один прохід, щоб відсортувати правильно.
[3, 2, 1] - У гіршому випадку в тому, що з 3 елементи сортуються у зворотному напрямку,
він збирається взяти 2 ітерацій для сортування.
Після однієї ітерації, це [2, 1, 3].
Другий дає впорядкований масив [1, 2, 3].
Таким чином, ви знаєте, ніколи не повинні йти через масив, в загальному,
більше, ніж N-1 разів, де п-число елементів у масиві.
Це називається Bubble Сортування тому, що найбільші елементи, як правило, «міхур вгору"
праворуч досить швидко.
Насправді, цей алгоритм має дуже цікаве поведінку.
>> Після т ітерацій через весь масив,
праві елементи м гарантовано
повинні бути відсортовані в їх правильному місці.
Якщо ви хочете в цьому переконатися,
ми можемо спробувати його на абсолютно зворотну список [9, 6, 5, 3, 2].
Після одного проходу через весь список,
[Звук письмовій формі]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
правий елемент 9 знаходиться в належному місці.
Після другої прохід, 6 матиме "пропускають вгору", щоб
другий праворуч місце.
Ці два елементи праворуч - 6 і 9 - буде в їх правильних місцях
Після перших двох прохід прохідні.
>> Отже, як ми можемо використовувати це, щоб оптимізувати алгоритм?
Ну, а після однієї ітерації по масиву
Ми насправді не потрібно перевіряти правий елемент
тому що ми знаємо, що це відсортовані.
Після двох ітерацій, ми знаємо напевно, сама права з двох елементів на місці.
Так, загалом, після до ітерацій повний масив,
Перевірка останнього до елементів є надлишковим, оскільки ми знаємо,
вони в потрібному місці вже.
>> Так що якщо ви сортування масиву з п елементів,
на першій ітерації - ви будете мати, щоб відсортувати всі елементи - перші п-0.
На другій ітерації, ви повинні дивитися на всі елементи, крім останнього -
перші N-1.
Інша оптимізація може бути, щоб перевірити, якщо список вже відсортований
після кожної ітерації.
Якщо він вже відсортовані, ми не повинні зробити більше ітерацій
за списком.
Як ми можемо це зробити?
Ну, якщо ми не робимо ніяких свопів на прохідній частині списку,
ясно, що цей список був вже відсортований, тому що ми не міняти нічого.
Таким чином, ми, безумовно, не повинні сортувати знову.
>> Може бути, ви могли б ініціалізувати прапор змінна називається "Не відсортовано до
помилковими і змінити його на істинний якщо у вас є, щоб обміняти будь-які елементи на
одна ітерація по масиву.
Або аналогічно, зробити зустрічну підрахувати, скільки свопів ви робите
на будь ітерації.
В кінці ітерації, якщо не поміняти будь-який з елементів,
Ви знаєте, в список вже відсортований, і все готово.
Bubble Сортування, як і інші алгоритми сортування, може бути
перероблені, щоб працювати для будь-яких елементів, які мають замовлення методом.
>> Тобто, при наявності двох елементів у вас є спосіб сказати, якщо перша
більше, рівне або менше, ніж другий.
Наприклад, ви можете відсортувати букви алфавіту, сказавши,
, Що <B, B <C, і т.д.
Або ви можете відсортувати дні тижня, де Неділя вважається менш понеділка
що менше, ніж у вівторок.
>> Bubble Сортування аж ніяк не дуже ефективні або швидкий алгоритм сортування.
У найгіршому випадку час роботи від батарей Big O н ²
тому що ви повинні зробити п ітерацій за списком
перевірка всіх п елементів, кожен прохід, пхп = п ².
Це час виконання означає, що як число елементів, ви сортуванні збільшується,
час виконання збільшується квадратично.
>> Але якщо ефективність не є головною турботою вашої програми
або якщо ви тільки сортування невеликого числа елементів,
Ви могли б знайти Bubble Сортування корисно, тому що
це один з найпростіших алгоритмів сортування, щоб зрозуміти
і код.
Це також відмінний спосіб отримати досвід роботи з перекладом теоретичних
алгоритм в реальному коді функціонування.
Ну, от і бульбашкового сортування для вас. Дякую за перегляд.
CS50.TV