>> [Мусиц плаиинг]
Даг Ллоид: Избор врста је алгоритам који, као што се може очекивати,
сортира низ елемената.
И алгоритам опозив је корак-по-корак комплет
упутстава за завршетак задатка.
>> У избору разврста Основна идеја је ово
наћи најмањи елемент и несортираног додајте га у крају сортирани списак.
Ефективно оно што ради је направљена сортирану листа, један елемент у једном тренутку.
Бреакинг га да псеудокоду можемо навести овај алгоритам
као што следи, понављам ово до нема унсортед елементи остају.
Претраживање по мусиц Подаци наћи најмању вредност,
онда замени најмању вредност са Први елемент неразврстан дела.
>> То може помоћи да се визуализују ово, па хајде да погледамо ово.
Дакле, ја тврдим, је мусиц низ и ја сам
указује да указивањем да је све елементи су црвене боје,
они још нису поредани.
Ово је цео мусиц део низа.
>> Дакле, идемо кроз кораке Избор врста за сортирање овај низ.
Дакле, опет цемо понављање док нема унсортед елементи остају.
Требаће претрагу кроз Подаци наћи најмању вредност,
и онда мењате ту вредност са Први елемент неразврстан дела.
>> Сада, опет, цела низ је део мусиц.
Сви црвених елемената мусиц.
Дакле, тражимо кроз и налазимо најмању вредност.
Почињемо на самом почетку, идемо до краја,
налазимо најмања вредност је један.
Дакле, то је први део.
А онда други део, замените ту вредност са први елемент несортираног дела,
или прва црвено елемент.
>> У овом случају то би било пет, тако да заменимо један и пет.
Када то урадимо, можемо визуелно види да смо
преселио најмањи елемент вредности од низа, на самом почетку.
Ефикасно сортирање тај елемент.
>> И тако смо заиста могу да потврдим и наводе да је један, сортира.
И тако ћемо указати на сортиране део нашег низа, бојењем је плава.
>> Сада смо само поновите поступак поново.
Ми тражимо кроз обичан део Низ да пронађе најмањи елемент.
У овом случају, то је два.
>> Ми свап да са првим елемент неразврстан дела.
У овом случају двојица су случајно први елемент неразврстан дела.
Тако смо свап два са себе, која заиста само оставља два
где је, и то је средјено.
Настављајући, тражимо кроз да пронађе најмањи елемент.
То је три.
Ми га замени са првим елемент, који је пет.
И сада три сортира.
>> Ми тражимо кроз поново, и ми наћи најмањи елемент је четири.
Ми га замени са првим елемента мусиц дио, а сада четири сортира.
>> Сматрамо да је пет најмањи елемент.
Ми га замени са првим елемент неразврстан дела.
И сада пет сортира.
>> И онда на крају, наш мусиц део се састоји
од само једног елемента, тако да тражимо кроз
и открили смо да је шест најмањи, а у ствари, једини елемент.
А онда можемо рећи да је средјено.
И сада смо укључен нашу низ од потпуног унсортед
у црвеном, у потпуности поредани у плавом, користећи одабира врсте.
>> Дакле, шта је ту је најгори сценарио?
Па у апсолутно најгори случај, морамо да погледамо преко
све елемената низа у наћи најмањи Унсортед елемент,
и морамо да поновимо овај процес н пута.
Једном за сваки елемент низа јер смо само у овом алгоритму,
Сорт један елемент у времену.
>> Шта је најбољи сценарио?
Па то је исто, зар не?
Ми заправо треба да и даље корак кроз сваки елемент низа
како би потврдили да је, у ствари, најмањи елемент.
>> Дакле најгорем случају рунтиме смо морам да поновим процес н пута,
једном за сваку од н елемената.
И у најбољем случају, морамо да урадимо исто.
>> Дакле, мислећи назад на нашу компјутерска комплексност Кутија за алат,
шта мислиш да је најгоре Случај Рунтиме за избор врсте?
Шта мислите је најбољи Случај Рунтиме за избор врсте?
>> Да ли сте погодите Биг О од н на квадрат, Велики и омега н на квадрат?
Био би у праву.
То су, у ствари, најгори случај и најбољи случај Рун
пута, за избор врсте.
>> Ја сам Доуг Лојд.
Ово је ЦС50.