[Грає музика] ДАГ Lloyd: Гаразд, бульбашкового сортування є алгоритм Ви можете використовувати для сортування набору елементів. Давайте поглянемо на те, як це працює. 

Таким чином, основна ідея бульбашкового сортування полягає в наступному. Як правило, ми хочемо, щоб рухатися вище значення елементів, як правило вправо, і знизити суму елементів, як правило ліворуч, як і слід було очікувати. Ми хочемо, щоб нижні речі, щоб бути в початок, і більш високі речі щоб бути в кінці. 

Як ми це робимо? Ну в псевдокоду коду, ми могли б сказати, давайте встановити лічильник на своп НЕ-нульове значення. Ми побачимо, чому ми робимо, що в секунду. А потім ми повторюємо наступні Процес поки лічильник не підкачки дорівнює 0, або поки ми не робимо ніяких свопи на всіх. 

Скидання підкачки лічильник 0, якщо це не вже 0. Тоді подивіться на кожен сусідній парою елементів. Якщо ці два елементи не в порядку, поміняти їх місцями, і додати 1 до прилавка підкачки. Якщо ви думаєте про це, перш ніж візуалізувати його, зауважити, що це буде рухатися нижче значення елементів зліва і вище цінується елементи права, ефективно робити те, що ми хочемо зробити, що рухатися ті групи елементів таким чином. Давайте собі, як це може виглядати за допомогою нашого масиву що ми використовували для тестування з цих алгоритмів. У нас є несортоване масив тут, вказує всі елементи перебуваючи в червоний колір. І я можу встановити лічильник підкачки в ненульове значення. Я вибрав довільно негативне 1-- це не 0. Ми хочемо, щоб повторити цей процес до лічильника підкачки не дорівнює 0. Ось чому я можу встановити своп врозріз з якоюсь ненульове значення, оскільки в іншому випадку Лічильник підкачки буде 0. Ми навіть не почати Процес алгоритму. Отже, ще раз, кроки are-- скинути лічильник підкачки 0, а потім подивитися на кожен поруч пара, і якщо вони не в порядку, обміняти їх, і додати 1 до прилавка підкачки. Отже, давайте почнемо цей процес. Тому перше, що ми робимо, це ми встановлюємо лічильник підкачки на 0, і тоді ми починаємо дивлячись на кожній суміжній пари. 

Так ми вперше почати дивитися на 5 і 2. Ми бачимо, що вони знаходяться поза замовити і тому ми поміняти їх місцями. І ми додаємо 1 до прилавка підкачки. Так що тепер наша підкачки лічильник 1, і 2 і 5 були включені. Тепер ми повторюємо цей процес знову. 

Ми дивимося на наступній суміжній пари, 5 і 1-- вони також вийшли з ладу, таким чином, ми поміняти їх і додати 1 до прилавка підкачки. Потім ми розглянемо 5 і 3. Вони вийшли з ладу, тому ми переставляємо їх і додати 1 до прилавка підкачки. Потім ми розглянемо 5 і 6. Вони в порядку, так що ми насправді не потрібно поміняти що-небудь в цей раз. Потім ми розглянемо 6 і 4. Вони також не в порядку, таким чином, ми поміняти їх і додати 1 до прилавка підкачки. 

Тепер зверніть увагу, що сталося. Ми переїхали 6 весь шлях до кінця. Таким чином, у виборі роду, якщо у Вас є видно, що відео, те, що ми робили, було ми закінчили переміщення маленькі елементи будівлі відсортований масив по суті з зліва направо, від меншого до більшого. У разі бульбашкового сортування, якщо ми після цього конкретного алгоритму, ми насправді збираєтеся будувати відсортований масив праворуч наліво, від більшого до меншого. Ми ефективно пропускають 6, Найбільше значення, весь шлях до кінця. 

І таким чином ми можемо оголосити сьогодні що це сортується, і в майбутньому iterations-- переживає масиву again-- ми не повинні розглядати 6 більше. У нас є тільки розглянути невідсортоване елементи коли ми дивимося на сусідніх пар. Таким чином, ми закінчили одне пройти через бульбашкового сортування. Так що тепер ми повернемося до питання, повторювати, поки лічильник заміни не дорівнює 0. Ну лічильник підкачки 4, так що ми збираємося щоб повторювати цей процес знову. 

Ми збираємося, щоб скинути лічильник підкачки 0, і дивитися на кожній суміжній пари. Отже, ми починаємо з 2 і 1-- вони в порядку, так що ми обміняти їх і ми додаємо 1 до прилавка підкачки. 2 і 3, вони в порядку. Нам не потрібно нічого робити. 3 і 5 в порядку. Нам не потрібно, щоб зробити що-небудь там. 

5 і 4, вони знаходяться поза порядку, і тому ми потрібно поміняти їх і додати 1 до прилавка підкачки. А тепер ми переїхали 5, другий за величиною елемент, до кінця несортованих частини. Так що тепер ми можемо назвати, що частина відсортованої частини. 

Тепер ви дивлячись на Екран і, ймовірно, може сказати, а я можу, що масив відсортовано прямо зараз. Але ми не можемо довести, що ще. Ми не маємо гарантію що це сортується. Але це, де своп Лічильник збирається вступити в гру. 

Таким чином, ми завершили прохід. Лічильник своп 2. Так що ми збираємося повторити цей процес знову, повторювати, поки лічильник заміни не дорівнює 0. Скидання лічильника підкачки 0. Таким чином, ми скинути його. 

Тепер подивимося на кожній суміжній пари. Це в порядку, 1 і 2. 2 і 3 в порядку. 3 і 4 знаходяться в порядку. Таким чином, на даний момент, зверніть увагу, ми завершили дивлячись на кожного сусідній пари, але лічильник своп раніше 0. 

Якщо ми не доведеться перемикатися будь-які елементи, то вони повинні бути в порядку, від Гідність цього процесу. І так що ефективність сортів, що ми любимо комп'ютерні вчені, Тепер ми можемо оголосити весь масив повинен бути розсортовані, тому що ми не зробили є, щоб поміняти будь-які елементи. Це дуже приємно. 

Так що в гіршому випадку Сценарій з бульбашкового сортування? У гіршому випадку масив У повністю зворотному порядку, і тому ми повинні один міхура великих елементів всього шлях через масив. І ми ефективно також повинні міхур всі маленькі елементи назад весь шлях через масив, теж. Таким чином, кожен з п елементів повинен рухатися за всіма іншими п елементів. Так що це найгірший сценарій. У кращому випадку сценарій, хоча це трохи відрізняється від вибору роду. Масив вже відсортовано коли ми йдемо в. Ми не повинні робити які-небудь свопи на першому проході. Таким чином, ми, можливо, доведеться шукати в меншій кількості елементів, правильно? Ми не повинні повторити це обробляти кілька разів. 

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

Якщо масив прекрасно відсортований хоча, ви тільки повинні дивитися один на елементів відразу. І якщо лічильник своп раніше 0, Ви можете сказати, що це масив відсортований. І так, в кращому випадку, це насправді краще, ніж вибір sort-- це омега п. 

Я Дуг Ллойд. Це CS50.