>> [Гуляе музыка]
Даг 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.