[Powered by Google Translate] [BUBBLE SORT] [JACKSON STEINKAMP Харвардския университет] [Това е CS50. CS50TV] Bubble Sort е пример за алгоритъм за сортиране - , която е процедура за сортиране набор от елементи в възходящ или низходящ ред. Например, ако искаш да сортирате масив, състоящ се от цифрите [3, 5, 2, 9], правилното прилагане на Bubble Sort ще се върне на сортират масив [2, 3, 5, 9] във възходящ ред. Сега, аз отивам да се обясни в pseudocode как работи алгоритъма. 

Да кажем, че ние сме сортиране списък на 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. Сега, нека да го напиша в pseudocode. По принцип, за всеки елемент в списъка, трябва да го погледнете и елемент директно в правото си. Ако те са от един спрямо друг - това е, ако елемент на ляво е по-голяма от тази в дясно - ние трябва да сменяте два елемента. 

Ние правим това за всеки елемент от списъка, и сме направили едно преминаване през. Сега ние просто трябва да направите преминаване през достатъчно пъти, за да се осигури списък е напълно правилно подредени. Но колко пъти трябва да премине през списъка, за да да се гарантира, че ние сме направили? Е, най-лошия случай е ако имаме напълно назад списък. След това е необходимо броят на преминаване технологична равен на броя на елементи N-1. Ако това не се връзва интуитивно, мисля, че на обикновен случай - списъка [2, 1]. 

Това ще отнеме един пас до сортирате правилно. [3, 2, 1] - най-лошия случай е, че с три елемента, сортирани назад, ще отнеме две повторения за сортиране. След една итерация [2, 1, 3]. Секунда дава подредени масив [1, 2, 3]. Така че, знаете, че никога не трябва да мине през масива, като цяло, повече от N-1 пъти, където N е броя на елементите на масива. Тя се нарича Bubble Sort, защото най-големите елементи не са "балон" правото доста бързо. В действителност, този алгоритъм е много интересно поведение. 

След метра повторения чрез целия масив, най-десните елементи м са гарантирани да бъдат подредени в правилното им място. Ако искате да видите това за себе си, можем да го пробвам на напълно назад списък [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 - ще бъде в правилните им места след първите две преминаване среда. 

Е, как може да използваме това, за да се оптимизира алгоритъма? Е, след една итерация чрез масив ние всъщност не трябва да се провери най-дясната елемент защото знаем, че сортирани. След две повторения, ние знаем, че най-десните два елемента са налице. Така че, като цяло, след к повторения чрез пълния набор, проверка на последните к е излишно, тъй като ние знаем те вече сте на правилното място. 

Така че, ако сте сортиране на масив от наш елементи, на първата итерация - ще трябва да сортирате всички елементи - първият N-0. На втората итерация, ще трябва да разгледаме всички елементи, но последната - първо N-1. Друг оптимизация може да се провери, ако списъкът е вече подредени след всяка итерация. Ако вече подредени, ние не трябва да направите повече повторения през списъка. Как можем да направим това? Е, ако ние не правим никакви суапове на преминаване на списъка, е ясно, че списъкът е вече подредени, защото ние не сменяте нищо. Така че ние определено не трябва да подреди отново. 

Може би бихте могли да инициализирате знамето променлива, наречена "подредени" лъжа и да я промените да е истина, ако имате да сменяте всички елементи на едно повторение чрез масив. , Нито по друг начин, да направи брояч колко суапове направите на всяко повторение. В края на итерация, ако не сменяте някой от елементите, ли, че списъкът е вече сортирани и сте готови. Сортирай Bubble, подобно на други алгоритми за сортиране, може да бъде променени, за да работи за всички елементи, които имат поръчване метод. 

Това е, като се има предвид два елемента имате начин да се каже, ако първият е по-голяма, равна или по-малко от втория. Например, бихте могли да сортирате букви от азбуката с думите че <б, б <в и др. Или можете да сортирате ден от седмицата, когато неделя е по-малко от понеделник което е по-малко от вторник. 

Bubble Sort никакъв случай не е много ефикасен и бърз алгоритъм за сортиране. Най-лошия случай по време на работа е Big O N ² защото трябва да се направи н повторения чрез списък проверка на всички н елементи всяко преминаване през nxn = N ². Тази писта означава, че времето, тъй като броят на елементите сортиране увеличава, време на изпълнение се увеличава quadratically. 

Но ако ефективност не е основна грижа на вашата програма или ако сте само сортиране на малък брой елементи, можете да намерите Bubble Sort полезна, защото това е един от най-простите алгоритми за сортиране, за да се разбере и код. То също е чудесен начин да получите опит с превода на теоретични алгоритъм в реалното функциониране код. Е, това е Bubble Sort за вас. Благодаря за гледане. CS50.TV