[Zenelejátszási] DOUG LLOYD: Selection sort egy algoritmus, ahogy az várható, rendezi egy sor elemet. És algoritmus visszahívás egy lépésről-lépésre sor Az utasítások egy feladat elvégzéséhez. 

A kiválasztás rendezni az alapötlet ezt, Keresse meg a legkisebb nem válogatott elem és add hozzá a végén a rendezett listát. Hatékonyan Mi ez épít egy rendezett lista, az egyik elem egy időben. Breaking le, hogy pszeudokódja állíthatnánk azt, ez az algoritmus az alábbiak szerint, ismételje meg ezt, amíg nem szétválogatott elem marad. Keresés a szétválogatás nélkül adatokat, hogy megtalálják a legkisebb értéket, majd cserélni a legkisebb érték a első eleme A szétválogatás nélkül részt. 

Segíthet, hogy megjelenítsék ezt, ezért vessünk egy pillantást erre. Tehát ez azt állítják,, egy szétválogatás nélkül tömb, és már jelezte azt jelezve, hogy minden Az elemek piros színű, még nincsenek rendezve. Ez az a teljes szétválogatás nélküli része a tömbben. 

Szóval menjünk a lépéseit kiválasztási sorrend rendezni ezt a tömböt. Tehát újra, meg fogjuk ismétlés amíg nem válogatott elemek maradnak. Csinálunk keresési keresztül adatokat, hogy megtalálják a legkisebb értéket, majd cserélni ezt az értéket a első eleme A szétválogatás nélkül részt. 

Most ismét a teljes tömb A rendezetlen része. Mind a piros elemek szelektálatlan. Tehát keresgélni és találjuk a legkisebb érték. Kezdjük az elején, megyünk a végén, találjuk a legkisebb érték, egy. Szóval ez is része az egyik. Aztán a második rész, a csere azt az értéket Az első elem a szétválogatás nélküli része, vagy az első piros elem. 

Ebben az esetben az lenne Öt, ezért cserélni egy és öt. Amikor ezt tesszük, amit lehet vizuálisan látni, hogy már költözött a legkisebb értékű elem A tömb, a legelején. Hatékonyan válogatás adott elem. 

És így valóban megerősítik, és kijelentik, hogy az egyik, van rendezve. És így fogunk tüntetni a rendezve része a mi tömb, színezés, hogy kék. 

Most már csak ismételjük meg a folyamatot újra. Mi keresni a szétválogatás nélküli része a tömb, hogy megtalálják a legkisebb eleme. Ebben az esetben, ez a két. 

Mi cserélni, hogy az első eleme a szétválogatás nélkül részt. Ebben az esetben két is előfordul, hogy Az első elem a szétválogatás nélkül részt. Tehát csere két önmagával, ami tényleg csak hagy két hogy hol van, és ez válogatni. Folytatva, amit keresni hogy megtalálják a legkisebb eleme. Ez három. Mi cserélni neki az első elem, amely öt. És most három rendezve. 

Mi keresgélni újra, és Keresse meg a legkisebb elem négy. Mi cserélni neki az első eleme a osztályozás nélküli része, és most négy rendezve. 

Azt látjuk, hogy az öt az A legkisebb eleme. Mi cserélni neki az első eleme a szétválogatás nélkül részt. És most öt rendezve. 

És akkor végül, mi szétválogatott része áll csak egyetlen elem, így keresni és azt látjuk, hogy hat a legkisebb, és valójában egyetlen eleme. És akkor azt mondhatjuk, hogy válogatni. És most már kapcsolva a tömb attól, hogy teljesen szétválogatott piros, teljesen rendezve kék, a kiválasztási sorrend. 

Szóval mi a legrosszabb forgatókönyv itt? Nos az abszolút legrosszabb esetben meg kell nézni fölött valamennyi elemét a tömb Keresse meg a legkisebb osztályozás nélküli elemet, és meg kell ismételni E folyamat n-szer. Miután minden egyes eleme a tömb mert csak ebben az algoritmus, Rendezés egyik eleme időpontban. 

Mi a legjobb esetben? Hát ez pontosan ugyanaz, ugye? Igazából az is átléphető minden egyes eleme a tömb annak érdekében, hogy erősítse meg, hogy, Tény, hogy a legkisebb elem. 

Tehát a legrosszabb esetben runtime, mi meg kell ismételni a folyamatot n-szer, egyszer minden n elem. És a legjobb esetben, van, hogy ugyanezt tegyék. 

Szóval gondoltam vissza a számítási komplexitás eszköztár, mit gondolsz a legrosszabb esetében futásidejű kiválasztási sorrend? Mit gondolsz a legjobb esetében futásidejű kiválasztási sorrend? 

Te hiszem Big O n faragva, és a Big Omega n faragva? Igazad van. Azok, sőt, a Legrosszabb esetben és a legjobb esetben távon szor, a kiválasztási sorrend. 

Én Doug Lloyd. Ez CS50.