[Powered by Google Translate] TOMMY: Vessünk egy pillantást a kiválasztási sort az algoritmus
meghozatalának számok listájának és rendezési őket.
Egy algoritmus, emlékszem, egyszerűen lépésről-lépésre
eljárás egy feladatra.
Az alapötlet mögött kiválasztási rendezés osztani
A lista két részre -
rendezett rész és egy válogatott részt.
Minden lépésnél a algoritmus, egy szám mozog-ból a
osztályozatlan része a rendezett részét, amíg végül a
teljes lista rendezésre.
Tehát itt van egy lista a hat szám -
23, 42, 4, 16, 8, és 15.
Most a teljes lista tekinthető rendezetlen.
Annak ellenére, hogy több, mint a május 16 már annak helyes
location, algoritmusunk nem tudhatja, hogy mindaddig, amíg a
teljes lista rendezésre.
Tehát mi úgy minden számot rendezetlen, amíg rendezni
magunk.
Tudjuk, hogy szeretnénk a listát, hogy növekvő sorrendben.
Tehát mi szeretnénk felépíteni a rendezett része a mi lista
balról jobbra, a legkisebbtől a legnagyobbig.
Ehhez, akkor meg kell találni a legkisebb rendezetlen elem
és tegye a végén a rendezett rész.
Mivel ez a lista nincs rendezve, az egyetlen módja, hogy az, hogy
nézd meg minden egyes elemet a rendezetlen rész, emlékezve
melyik eleme a legalacsonyabb és összehasonlítása
minden elem e.
Tehát akkor először nézd meg a 23.
Ez az első elem, láttuk, így emlékezni fogunk
rá, mint a minimális.
Ezután megnézzük, 42.
42 nagyobb, mint 23, így a 23 még mindig a minimális.
Ezután a 4, ami kevesebb, mint 23, ezért fogunk emlékezni 4
az új minimum.
Következő 16, amely nagyobb, mint 4, SO 4-
még mindig a minimális.
8 nagyobb, mint 4, és 15 nagyobb, mint 4, SO 4-kell
a legkisebb rendezetlen elem.
Tehát annak ellenére, hogy, mint az emberek akkor rögtön láthatjuk, hogy a 4.
a legkisebb elem, a mi algoritmus kell nézni
minden rendezetlen elem, még azután is, hogy megtalálta a 4 - a
minimum elem.
Tehát most, hogy megtaláltuk a legkisebb elem, 4, akkor szeretnénk
hogy helyezze át a rendezett része a listán.
Mivel ez az első lépés, ez azt jelenti, akarjuk helyezni 4-es
A lista elején.
Most a 23. elején a lista, így a
nézzük cserélni a 4 és a 23.
Tehát most A lista így néz ki.
Tudjuk, hogy a 4-ben kell, hogy legyen a végleges helyére, mert
mind a legkisebb elem és az elem elején
a lista.
Tehát ez azt jelenti, hogy mi soha nem kell mozgatni újra.
Szóval ismételje meg ezt a folyamatot, hogy egy újabb elemet a
rendezett része a listán.
Tudjuk, hogy nem kell, hogy nézd meg a 4, mert
már rendezve.
Így tudjuk kezdeni a 42, amit majd emlékezni, mint a
minimum elem.
Így a következő fogjuk nézni a 23, ami kisebb, mint 42, így
emlékszem 23 az új minimum.
Azután látjuk a 16, amely nem kisebb, mint 23, így
16 az új minimum.
Most nézd meg a 8, amely kevesebb, mint 16, így
8 az új minimum.
És végül 8 kisebb, mint 15, így tudjuk, hogy a 8. egy minimum
rendezetlen elem.
Tehát ez azt jelenti, hogy meg kell csatolnia a 8 rendezve
részét a lista.
Most 4 az egyetlen rendezett elem, ezért szeretnénk helyezni
a 8 mellett a 4.
Mivel a 42 az első elem a rendezetlen része a
listában, akkor szeretnénk cserélni a 42 és a 8.
Tehát most A lista így néz ki.
4. és 8. képviseli a rendezett részét a jegyzék, és a
fennmaradó számok a rendezetlen
részét a lista.
Szóval továbbra is egy másik iteráció.
Kezdjük 23 ebben az időben, hiszen nem kell nézni
a 4 és a 8 többé, mert már
már rendezve.
16 kevesebb, mint 23, ezért fogunk emlékezni
16 az új minimum.
16 kisebb, mint 42, de 15 kevesebb, mint 16, így 15 kell, hogy legyen
a minimális rendezetlen elem.
Tehát most szeretnénk cserélni a 15 és az 23-
nekünk ezt a listát.
A rendezett része a csoportba tartoznak az a 4., 8. és 15., valamint
ezek az elemek még mindig rendezetlen.
De ez csak azért történik, hogy a következő rendezetlen elem, 16,
már rendezve.
Azonban nincs mód a mi algoritmus tudni, hogy a 16
már a megfelelő helyen, ezért kell még
ismételje meg pontosan ugyanazt a folyamatot.
Látjuk tehát, hogy a 16. kisebb, mint 42, és 16 kisebb, mint 23, így
16 kell, hogy legyen a minimum elem.
Lehetetlen, hogy ezt az elemet cserélni önmagával, így tudjuk
egyszerűen hagyja ezt a helyet.
Tehát szükség van egy több lépéses a mi algoritmus.
A 42 23-nál nagyobb, tehát 23 kell, hogy legyen a
minimum rendezetlen elem.
Amint cserélni a 23 és a 42, akkor a végén a mi végső
rendezett lista -
4, 8, 15, 16, 23, 42.
Tudjuk, hogy 42 kell a megfelelő helyre, mivel ez a
egyetlen eleme maradt, és ez kiválasztás sort.
Nézzük most hivatalossá algoritmusunk néhány
pszeudokód.
On line on, azt látjuk, hogy meg kell integrálni felett
minden eleme a listán.
Kivéve az utolsó elem, mivel az 1 elem
lista már rendezve.
On line kettő, úgy véljük, az első eleme a válogatott
része a listát, hogy a minimum, mint mi a mi
Például, így van valami összehasonlítani.
Vonal 3 kezdődik a második kör, melyben iterációkhoz
egyes rendezetlen elem.
Tudjuk, hogy miután én iteráció, a rendezett rész
Az A lista kell i elemek, mióta minden lépésben
rendezések egyik eleme.
Tehát az első válogatott elemnek kell lennie helyzetben i plusz 1.
On line négy, összehasonlítjuk az aktuális elem a minimum
elem, amit eddig láttunk.
Ha az aktuális elem kisebb, mint a minimális
elem, akkor emlékezni az aktuális elem, mint az új
minimum on line öt.
Végül, a vonalakon hat és hét, akkor cserélje ki a minimum
elem az első szelektálatlan elem, ezáltal
hozzátéve, hogy a rendezett része a listán.
Ha van egy algoritmus, egy fontos kérdést feltenni
magunkat, mint programozó is, hogy mennyi ideig volt, hogy az el?
Majd 1. tennünk a kérdést, hogy mennyi ideig tart, ezt a
algoritmus fut a legrosszabb esetben?
Recall általunk képviselt ez futás
idő nagy O jelölést.
Annak megállapítása érdekében, a minimális rendezetlen elem, mi
lényegében kellett összehasonlítani egyes elem a listán
minden más elem a listában.
Intuitíve, ez úgy hangzik, mint egy O n négyzetes működését.
Keresi a mi pszeudokód, mi is van egy loop beágyazva
egy hurok, ami valóban úgy hangzik, mint egy O
n négyzet működését.
Azonban ne feledjük, hogy nem kell, hogy nézd át a
teljes lista meghatározása során minimum rendezetlen elem?
Miután tudta, hogy a 4-es rendezett, például, hogy nem
kell, hogy nézd meg újra.
Így működik ez alacsonyabb a működési idő?
A mi listáját hossza 6, mi szükséges ahhoz, hogy 5
összehasonlítást az első elem, négy összehasonlítások
A második elem, és így tovább.
Ez azt jelenti, hogy a lépcsőfokok számát az összege
az egész szám 1-től a hossza a jegyzék mínusz 1.
Mi lehet képviseli ezt a összegzésben.
Nem fogunk belemenni összegzések itt.
De kiderült, hogy ez az összegzési egyenlő n-szer
n mínusz 1 több mint 2.
Vagy azzal egyenértékű, n kockás több mint 2 mínusz n több mint 2.
Amikor beszélünk, aszimptotikus futási e n kockás kifejezés
fogja uralni ezt a n kifejezést.
Szóval kiválasztás rendezés O n négyzeten.
Emlékezzünk vissza, hogy a mi példánkban, a kiválasztási sorrend továbbra is szükség van
ellenőrizheti, hogy egy számot már rendezve
kellett mozgatni.
Tehát ez azt jelenti, hogy ha mi futott kiválasztás sort felett már
rendezett lista, szükség lenne az azonos lépések számát, mivel
lenne, ha fut egy teljesen rendezetlen listát.
Szóval kiválasztás sort egy legjobb esetben teljesítményt n négyzetes,
amit képviselnek, azzal omega n négyzeten.
És ez a fajta kiválasztás.
Csak egy a sok algoritmusok tudunk
használja, hogy rendezni egy listát.
A nevem Tommy, és ez CS50.