>> [Мусиц плаиинг]
Даг Ллоид: У реду, балон врста је алгоритам
можете користити за сортирање скуп елемената.
Хајде да погледамо како се то ради.
>> Дакле, основна идеја балон врста је ово.
Ми генерално желите да преместите више вреднује елементи углавном десно,
и смањити углавном у вредности елемената са леве стране, као што смо очекивали.
Желимо ниже ствари буду на почетак, и више ствари
бити на крају.
>> Како ми то радимо?
Па у Псеудокод код, можемо рећи, хајдемо
сет свап цоунтер то нон-нула вредности.
Видећемо зашто то чинимо у секунди.
И онда поновити сљедеће Процес док Свап бројач је 0,
или док не правимо свопови уопште.
>> Ресет свап цоунтер то 0 ако већ није 0.
Онда погледате сваки суседни пар елемената.
Ако та два елемента су Не би, замените их,
и додаје 1 свап шалтеру.
Ако размишљате о ово пре него што га замишљали,
Приметићете да ће овај потез ниже цењеним елементи за лево
и више вреднује елементе десно, ефикасно раде оно што желимо да урадимо,
која је померите те групе елемената на тај начин.
Хајде да визуализовати како је могу изгледати користећи наш низ
који смо користили за тестирање од ових алгоритама.
Имамо низ УНСОРТЕД опет овде, указују све елементе
бити у црвено.
И сет ми свап цоунтер до нуле вредности.
Ја произвољно одабрао негативна 1-- није 0.
Желимо да поновимо овај процес док свап шалтеру је 0.
То је разлог зашто сам поставио свој свап супротности са неким не-нула вредности,
јер у противном Свап бројач ће бити 0.
Не би ни отпочне процес алгоритма.
Дакле, опет, кораци су-- ресет свап цоунтер
0, онда погледајте сваки суседни пар, и ако су у реду,
свап их и додајте 1 на свап шалтеру.
Дакле, хајде да почнемо овај процес.
Дакле, прва ствар коју радимо је поставили смо свап бројач на 0,
и онда почни на сваком суседном пару.
>> Зато смо прво почети гледајући 5 и 2.
Видимо да су из нареди па смо их заменимо.
И додамо 1 до свап шалтеру.
Дакле, сада наш Свап бројач је 1, и 2. и 5 су пребачене.
Сада поновите поступак поново.
>> Гледамо на следећем суседном пару, 5 и 1-- су такође ван функције,
тако да их мењате и додајте 1 уз своп шалтеру.
Онда погледамо 5 и 3.
Они су од реда, па смо свап их и додамо 1 до свап шалтеру.
Онда погледамо 5. и 6..
Они су у реду, тако да заправо не треба да замени било шта овај пут.
Онда погледамо 6 и 4.
Такође су од реда, па смо свап их и додамо 1 до свап шалтеру.
>> Сада погледајмо шта се догодило.
Ми смо преселили 6 скроз до краја.
Дакле, у избор врсте, ако сте види тај видео, оно што смо урадили је
смо завршили померање Најмањи елементи у згради
сортиран низ суштински од лева на десно, најмањег до највећег.
У случају балон врсте, ако смо Следећи овом алгоритма,
ћемо заправо да се гради сортиран низ од десне стране
на лево, највећег ка најмањем.
Ми смо ефикасно у мехурићима 6, Највећа вредност, све до краја.
>> И тако сада можемо прогласити да је се разврстава,
и у будућности итератионс-- пролази кроз низ Поново:
не морамо више да размотри 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, можете рећи низ сортира.
И тако у најбољем случају, ово је заправо бољи од селекције
сорт-- је омега н.
>> Ја сам Доуг Лојд.
Ово је ЦС50.