[Powered by Google Translate] ТОММИ: Хајде да погледамо на избор врсте, алгоритам
за узимање листу бројева и сортирање их.
Алгоритам, сетите се, једноставно корак-по-корак
Поступак за остваривање задатка.
Основна идеја која стоји иза избора врсте је да подели
Наша листа на два дела -
сортирано део и некласификовани део.
На сваком кораку алгоритма, број премештена из
некласификовани део на сортираног дела док се на крају
Цела листа се сортирају.
Дакле, овде је списак од шест бројева -
23, 42, 4, 16, 8, и 15.
Сада је цела листа се сматра несортиран.
Иако број као 16 можда већ у његов исправан
локацију, наш алгоритам нема начина да сазна да је до
Цела листа се сортирају.
Тако ћемо размотрити сваки број се несортиран док смо сортирали
то сами.
Знамо да желимо списак буде у растућем редоследу.
Тако ћемо желети да изгради сортирани део наше листе
слева на десно, најмање до највеће.
Да бисте то урадили, ми ћемо морати да нађемо минимум несортиран елемент
и ставио га на крају сортираног дела.
Пошто ова листа није сортирана, једини начин да се то уради је да се
погледајте сваки елемент у некласификовани дела, сећајући
који елемент је најнижи и поређења
сваки елемент то.
Дакле, прво ћемо погледати на 23 године.
Ово је први елемент смо видели, па ћемо запамтити
је као минимум.
Следеће што ћемо гледати на 42.
42 је већи од 23, па 23 је и даље минимална.
Следећи је 4 који је мање од 23, па ћемо запамтити 4
као нови минимум.
Следећа је 16 која је већа од 4, па 4
је и даље минимална.
8 је већи од 4, а 15 је већи од 4, па 4 мора бити
Најмањи некласификовани елемент.
Дакле, иако је као људи одмах можемо видети да је 4
минимална елеменат, наш алгоритам треба да погледамо
сваки елемент некласификовани, чак и након што смо пронашли 4 -
минимална елемент.
Дакле, сада смо нашли минимум елемент, 4, ми ћемо желети
да преместите га у сортираном делу листе.
Пошто је ово први корак, то значи да желимо да се стави на 4
почетак листе.
Сада 23 је на почетку листе, па
хајде да променим 4 и 23.
Дакле, сада је наша листа изгледа овако.
Знамо да 4 буде у својој завршној локацији, јер је
и најмањи елемент и елемент на почетку
листе.
Дакле, ово значи да ми никада не треба да га удаљи.
Дакле, хајде да поновите овај поступак да бисте додали још један елемент на
сортирана део листе.
Ми знамо да не треба да гледају на 4, јер је
Већ сортирају.
Дакле, ми можемо почети у 42, што ћемо запамтити као
минимална елемент.
Дакле, следећи ћемо погледати на 23 што је мање од 42, тако да смо
запамтите 23 је нови минимум.
Следеће што видимо 16 што је мање од 23, тако да
16 је нови минимум.
Сада гледамо 8 који је мањи од 16, тако да
8 је нови минимум.
И на крају 8 је мање од 15, тако да знамо да је 8 је минимална
некласификовани елемент.
Значи треба додати 8 до сортиран
Део листе.
Сада 4 је једини сортиран елемент, па смо желели да поставите
је 8 поред 4.
Пошто 42 је први елемент у некласификовани делу
Списак ћемо желети да променим 42 и 8.
Дакле, сада је наша листа изгледа овако.
4 и 8 представљају сортирани део листе, као и
Преостали бројеви представљају унсортед
Део листе.
Дакле, хајде да наставимо са другим итерације.
Почињемо са 23 овај пут, јер не морамо да погледамо
је 4 и 8 више, јер су њих двојица
већ сређено.
16 је мање од 23, па ћемо запамтити
16 као нови минимум.
16 је мања од 42, али 15 је мања од 16, па 15 мора бити
минимална некласификовани елемент.
Дакле, сада желимо да променим 15 и од 23 до
дајте нам ову листу.
Сортиран део листе састоји од 4, 8 и 15, као и
ови елементи су увек несортиран.
Али тако једноставно дешава да следећи некласификовани елемент, 16,
је већ сређено.
Међутим, не постоји начин за нашу алгоритма да знају да 16
је већ у својој одговарајућој локацији, тако да и даље треба да
Понављам потпуно исти процес.
Дакле, видимо да је 16 мање од 42, а 16 је мање од 23, тако да
16 мора да буде минимум елемент.
Немогуће је да замените овај елемент са собом, тако да можемо
једноставно оставити на овој локацији.
Зато нам треба још један пас нашег алгоритма.
42 је већи од 23, па 23 мора да буде
минимална некласификовани елемент.
Када смо мењати 23 и 42, можемо завршити са наш коначни
сортирана листа -
4, 8, 15, 16, 23, 42.
Знамо 42 мора да буде на правом месту, јер је то
Једини елемент лево, а то је селекција врста.
Хајде сада формализује свој алгоритам са неким
Псеудокод.
На линији један, можемо да видимо да је потребно да се интегришу у
сваки елемент листе.
Осим последњег елемента, пошто је 1 елемент
Списак је већ сређено.
На линији два, сматрамо да је први елемент унсортед
део листе буде минимална, као што смо урадили са нашим
На пример, тако да морамо нешто да упореде то.
Линија три почиње другу петљу у којој смо прелазили преко
свака некласификовани елемент.
Ми знамо да када сам итерација, сортиран део
нашег листи мора да сам елементи у њој од сваког корака
сортира један елемент.
Дакле, прво некласификовани елемент мора бити у позицији ја, плус 1.
На линији четири, упоредимо тренутну елемент на минимум
елемент који смо до сада видели.
Ако је тренутни елемент је мања од минималне
елемент, онда се сетимо тренутни елемент као нова
минимална на линији пет.
Коначно, на линијама шест и седам, ми мењати минимум
елемент са првом некласификовани елемента, чиме
додајући да је у сортираном делу листе.
Када имамо алгоритам, важно питање да поставим
себе као програмере је колико је то трајати?
Прво ћемо се поставити питање колико је потребно за то
алгоритам да се приказују у најгорем случају?
Рецалл заступамо овај ток
Време са великим О нотацији.
У циљу утврђивања минималне Унсортед елемент, ми смо
суштини морао да упореди сваки елемент у листи
сваки други елемент у листи.
Интуитивно, ово звучи као О н квадрат рада.
Гледајући наше Псеудокод, ми такође имамо петљу угнежђену унутра
друга петља, која заиста звучи као О
од н квадрат рада.
Међутим, имајте у виду да ми не треба да се пази на
цела листа приликом одређивања минималне несортиран елемент?
Када смо знали да је 4 је сортиран, на пример, нисмо
Треба да погледате поново.
Значи ли то нижа време рада?
За нашу листу дужине 6, морали смо да се пет
поређења за први елемент, четири поређења за
Други елемент, и тако даље.
То значи да је укупан број корака је збир
целих бројева од 1 до дужине листе минус 1.
Можемо представљају ово са збирно.
Нећемо ићи у сумматионс овде.
Али испоставило се да је ова сума једнака н пута
н минус 1 над 2.
Или еквивалентно, н квадрат преко 2 минус н преко 2.
Када говоримо о асимптотска рунтиме, ово н квадрат термин
ће доминирати овом н мандат.
Дакле, избор врста је О од н квадрат.
Подсетимо да је у нашем примеру, избор врста и даље потребно да
проверите да ли број који је већ сортиране
потребно да се помера.
То значи да, ако смо трчали за избор врсте у већ
сортирана листа, то би захтевало исти број корака као што је
би када ради у потпуно некласификовани листе.
Дакле, избор врста има најбољи учинак случај од н квадрата,
које представљају са омега н квадрат.
И то је за избор врсте.
Само један од многих алгоритама се иден
користе да сортирате листу.
Моје име је Томи, а ово је цс50.