[Muzikos grojimo] Doug LLOYD atranka Rūšiuoti yra algoritmas, kuris, kaip galima tikėtis, rūšiuoja iš elementų rinkinį. Ir algoritmas Prisiminkite yra žingsnis po žingsnio rinkinys Nurodymų pildymo užduotį. 

Be atrankos rūšiuoti Pagrindinė idėja yra tai, Raskite mažiausią nerūšiuotas elementą ir įtraukti ją į išrūšiuotų sąrašo gale. Efektyviai Kas tai yra statyti rūšiuotą sąrašas, vienas elementas, tuo pačiu metu. Karščiausios jį žemyn Pseudocode galėtume teigti, šį algoritmą taip, pakartokite šį iki nėra nerūšiuotos elementai išlieka. Paieška per nerūšiuotų duomenų rasti mažiausią vertę, tada apsikeitimo mažiausią vertę su pirmasis elementas nerūšiuotųomis dalis. 

Jis gali padėti vizualizuoti tai, todėl galime imtis į tai žiūrėti. Taigi, tai, aš teigia, yra nerūšiuotų masyvo ir aš nurodyta, kad, nurodant, kad visi iš elementų yra raudoni, jie yra dar rūšiuojami. Tai yra visa nerūšiuotų dalis masyvo. 

Taigi eikime per žingsnių pasirinkimas rūšiuoti rūšiuoti šio masyvo. Taigi dar kartą, mes gonna kartojimą kol nėra nerūšiuotos elementai išlieka. Mes gonna paiešką per duomenų rasti mažiausią vertę, ir tada sukeisti šią vertę su pirmasis elementas nerūšiuotųomis dalis. 

Dabar, vėlgi, visa masyvas yra nerūšiuotos dalis. Visi raudonų elementų yra nerūšiuotos. Taigi, mes ieškoti ir randame mažiausią vertę. Mes pradėti iš pradžių, mes einame iki galo, randame mažiausios vertės yra viena. Štai pirmoji dalis. Ir tada antroji dalis, apsikeitimo šią vertę su pirmasis elementas nerūšiuotųomis dalis, arba pirmą raudona elementas. 

Šiuo atveju, kad būtų penki, todėl mes apsikeitimo vienerių ir penkerių. Kai mes tai darome, mes galime vizualiai matyti, kad mes persikėlė mažiausią vertinami elementą masyvo, į pačią pradžią. Efektyviai rūšiavimo, kad elementas. 

Ir todėl mes galime iš tiesų patvirtina, ir nurodyti, kad vienas yra rūšiuojami. Ir todėl mes nurodyti surūšiuoti dalis mūsų masyvas, kurį dažymas jis mėlynas. 

Dabar mes tiesiog vėl pakartokite šį procesą. Ieškome per nerūšiuotų dalis masyvas rasti mažiausią elementą. Šiuo atveju, tai du. 

Mes apsikeitimo, kad su pirmuoju elementas nerūšiuotųomis dalis. Šiuo atveju du taip pat atsitinka būti pirmasis elementas nerūšiuotųomis dalis. Taigi, mes apsikeitimo du su savimi, kuri tikrai tik palieka du kur ji yra, ir tai rūšiuojami. Tęsiant, mes ieškoti rasti mažiausią elementą. Tai trys. Mes sukeisti su pirmuoju elementas, kuris yra penki. O dabar trys yra rūšiuojami. 

Mes ieškoti dar kartą, ir mes rasti mažiausias elementas yra keturi. Mes sukeisti su pirmuoju elementu nerūšiuotų dalis, o dabar keturi rūšiuojamos. 

Manome, kad penki yra mažiausias elementas. Mes sukeisti su pirmuoju elementas nerūšiuotųomis dalis. Ir dabar penkios yra rūšiuojami. 

Ir tada galiausiai, mūsų nerūšiuotų dalį sudaro tiesiog vieno elemento, todėl mes ieškoti ir matome, kad šeši yra mažiausias, ir iš tikrųjų, tik elementas. Ir tada mes galime teigti, kad ji yra rūšiuojami. Ir dabar mes perėjo mūsų masyvas iki galo Nerūšiuotos raudonai, visiškai rūšiuojami mėlyna, naudojant atrankos rūšiuoti. 

Taigi, kas blogiausiu atveju čia? Na absoliutus blogiausias atveju, mes turime pažvelgti per visi iš masyvo elementų iki Raskite mažiausią nerūšiuotas elementas, ir mes turime kartoti šis procesas n kartų. Kai kiekvienam masyvo elementą nes mes tik, šiuo algoritmu, Rūšiuoti vienas elementas metu. 

Koks geriausias scenarijus? Na tai lygiai tas pats, tiesa? Mes iš tikrųjų turime dar žingsnis per kiekvienas elementas masyve siekiant patvirtinti, kad ji yra, Iš tiesų, mažiausias elementas. 

Taigi blogiausiu atveju Runtime, mes turi pakartoti procesą n kartų, vieną kartą kiekvienas iš n elementų. Ir geriausiu atveju, turime padaryti tą patį. 

Taigi galvoju grįžti į mūsų skaičiavimo sudėtingumas rinkinys, ką jūs manote yra blogiausia atveju Veikimo atrankos rūšiuoti? Ką manote yra geriausias atveju Veikimo atrankos rūšiuoti? 

Ar galite atspėti, Big O n kvadratu, Big omega n kvadratu? Jūs norite būti teisus. Tie, iš tiesų, blogiausiu atveju ir geriausias atvejis paleisti kartų, dėl atrankos rūšiuoti. 

Aš Doug Lloyd. Tai CS50.