МАРК грозен-СМИТ: Здраво, ја сам Марк Грозен-Смитх, а то је Куицксорт. Баш као и уметања врсте балона врста, Куицксорт је алгоритам за сортирање листе или низ ствари. Због једноставности, претпоставимо да су они ствари су само цели бројеви, али Знам да ради за Куицксорт више него само бројеви. Сцхнеллстарт је мало компликованији него уметање или мехур, али то је такође много ефикаснији у већини случајева. Чекај мало. Да ли је он то рекао "највише случајева, "не" све "? Интересантно, бр. Нису сви случајеви су исти. Не брините о овом детаљ ако вам нису видели Биг О нотацију још, али Куицксорт је О (н на квадрат) алгоритам у најгорем случају, баш као уметања или балон врста. Међутим, обично делује много као стари аналогни м алгоритма. Зашто? Вратићемо се на то касније. Али за сада, хајде да уче како Куицксорт функционише. 

Дакле, хајде да хода кроз ово Куицксортинг низ целих бројева од најмањег до највеће. Овде имамо целих бројева 6, 5, 1, 3, 8, 4, 7, 9, и 2. Прво, бирамо коначан елемент Овај низ - у овом случају, два - и позвати да је "пивот." Даље, почети да погледате две ствари - један, најнижи индекс, који ћу упутити као бораве десно од зид, и, два, крајње леви елеменат, који ћу назвати "струја елемента. "Шта ћемо да урадимо је да погледати све остале елементе, друге од стожер, и стави све елементе мањи него у зглобу лево од зида и свих оних већи од стожер на Право на зиду. Затим, на крају, ми ћемо одустати од пивот Право на том зиду да га стави између сви бројеви мањи од њега и све већи бројеви. 

Дакле, хајде да урадимо то. Покупите 2, ставио на зид почетак, и позвати 6 "струју елемента. "Зато желимо да погледате наш тренутни елемент, 6. И пошто је већи од 2, ми смо га оставити тамо да Право на зиду. Затим, идемо на погледајте 5 као наш Садашњи елемент и види да је овај је, опет, већи од стожер, па смо оставите га где је на десној страни страни зида. Ми идемо даље. Наш тренутни елемент је сада 1, и - ох. Ово је другачије. Садашњи елемент је сада мањи него пивот, па смо желели да га стави лево од зида. Да бисте то урадили, хајде да само пребаците струја елемент са најнижом индекса седи само на десно од зида. Сада, идемо горе зид једне индекса тако да 1 је на левој страни страни зида сада. 

Чекај. Управо сам помешао елементе на десна страна зида, зар не? Не брини. То је у реду. Једино ми је стало за сада је да су сви ови елементи на Право на зиду су већи од вешања. Не прави ред је увек претпоставља. 

Сада, назад на сортирање. Дакле, ми смо и даље на гледајући остатак елемената. И у овом случају, видимо да постоје нема других елемената мање од пивот, тако да смо их све оставити на десна страна зида. Коначно, долазимо до тренутног елемента и види да је стожер. Сада, то значи да имамо две делови низа, први је мали на стожер и на левој страни зида, а други бића већи од стожер на десна страна зида. Желимо да стави пивот елемент између два, а онда ћемо знати да стожер је у свом правом Коначна сортирана место. Тако да смо се пребацили на први елемент десна страна зида са пивот, а ми знамо да стожер у свом десном положају. 

Ми онда поновите овај процес за субарраис лево и десно од вешања. Пошто је последња субарраи је само један дуго елеменат, знамо да је то већ Сортед јер како можете бити ван нареди ако си само један елемент? За десне стране субарраи, ми види да је стожер 5, и Тхе Валл је само остало од 6. И струја елемент такође почиње као 6. Дакле, 6 је већи од 5. Ми га оставити тамо где је на десна страна зида. Сада, креће на, 3 је мања од 5. Тако да смо га пребацили са првог елемента само право на зид. Сада, преселио сам зид још један. Сада, креће се на 8.. 8 је већи од 5, и тако смо га оставили. 4 је мање од 5, па смо га пребацили. И на. И на. 

Сваки пут када поновите процес на леве и десне стране низа. ми одабрати пивот и урадите поређења и створити још један ниво лево и десна субарраис. Ово рекурзивни позив ће се наставити све док смо до краја када смо подели укупан низ у само субарраис дужине 1. Одатле, ми знамо низ је сортиран јер сваки елемент има, у неки бод, био стожер. Другим речима, за сваки елемент, све бројеви са леве стране су мање вредности и сви бројеви до Право имају веће вредности. 

Овај метод функционише веома добро ако Вредност стожер изабраног је отприлике у средини опсег вредности листе. То би значило да, након крећемо елементи око, тамо око колико елементи са леве стране пивот као што постоје са десне. И дивиде-и-владај природа Куицксорт алгоритам се онда узима пун предност. Ово ствара рунтиме за О (н лог н,) н зато морамо да урадимо н минус 1 поређења на свакој генерацији и лог н зато морамо да поделимо листу лог н пута. Међутим, у најгорим случајевима, то алгоритам заправо може бити О (н квадрат) Претпоставимо на свакој генерацији., стожер само тако се дешава да се најмањи или највећи Бројеви смо сортирање. То би значило разбије листу н пута и израда н минус 1 поређења сваки пут. Тако, о н квадрат. 

Како можемо побољшати начин? Један добар начин да се побољша метод је да смањи вероватноћу да рунтиме је икада заправо о н квадрат. Запамтите ово најгоре, најгори могући сценарио може да се догоди само када пивот изабран је увек највиши или најнижа вредност у низу. Да би се обезбедило да је мање вероватно да ће се десити, можемо наћи осовину од избора више елемената и узимање средње вредности. 

Моје име је Марко грозен-Смит, и то је ЦС50. 

Због једноставности, претпоставимо да су они ствари су само цели бројеви, али Знам тај Куицксерт - Куицксерт? Извините. 

Овде имамо целих бројева 6, 5, 1, 3, 8, 4, 9. 

ПРЕДСЕДНИК 1: Стварно? 

ПРЕДСЕДНИК 2: Немој тамо зауставити. 

ПРЕДСЕДНИК 1: Стварно?