[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.