[Powered by Google Translate] [Beillesztés Sort] [Tommy MacWilliam] [Harvard Egyetem] [Ez CS50.TV] Vessünk egy pillantást a beszúrási sort, egy algoritmus vesz egy listát a számok és rendezési őket. Egy algoritmus, emlékszem, egyszerűen lépésről-lépésre eljárást egy feladatra. Az alapötlet mögött helyezés sort, hogy ossza meg 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 A rendezetlen részletben a rendezett rész míg végül a teljes lista rendezésre. Itt látható a lista a hat szelektálatlan szám - 23, 42, 4, 16, 8, és 15. Mivel ezek a számok nem minden emelkedő sorrendben, ők rendezetlen. Mivel még nem kezdődött válogatás még, akkor figyelembe mind a hat elemet a rendezetlen részét. 

Ha egyszer elkezdünk válogatás fogjuk, hogy ezeket a számokat rendezve balra ezeket. Nos, kezdjük a 23, az első eleme a listában. Jelenleg nincs olyan eleme a mi rendezett részén még úgyhogy csak úgy 23, hogy a kezdetét és végét a sorrendje részét. Most, a rész szerint rendezve van egy szám, 23, és a válogatott része van az öt számot. Nézzük most, illessze be a következő számot a mi rendezetlen rész, 42, a rendezett rész. 

Ehhez szükségünk lesz összehasonlítani a 42 a 23 - az egyetlen eleme a rendezett rész eddig. Negyvenkét nagyobb, mint 23, így egyszerűen fűzze 42 a vége A rendezett részének a listán. Nagyszerű! Most a válogatott rész két eleme, és a válogatott rész négy elemet. Szóval, most már mozog a 4, a következő elem a rendezetlen rész. Szóval, hol kell ezt helyezni a rendezett rész? 

Ne feledje, hogy szeretnénk helyezni ezt a számot rendezetten így a válogatott része továbbra is helyes sorrendje minden alkalommal. Ha helyezzük a 4 jobbra a 42, akkor a lista lesz elromlott. Nos, nézzük tovább halad jobbról balra a mi rendezési részletben. Ahogy haladunk, menjünk műszak minden szám le a helyet, hogy helyet csináljon az új számot. Oké, 4 is kevesebb, mint 23, így nem tudunk elhelyezni itt sem. Menjünk a 23 megfelelő egy helyen. 

Ez azt jelenti, hogy szeretné helyezni a 4 az első slot a rendezett rész. Figyeljük meg, hogy ezt a helyet a listán már üres, mert mi már mozgó elemek sorrendje meghatározott, ahogy már találkozott velük. Rendben van. Szóval, mi vagyunk félúton. Folytassuk algoritmusunk behelyezésével a 16 a rendezett rész. Tizenhat kisebb, mint 42, úgyhogy váltani a 42 jobbra. Tizenhat is kevesebb, mint 23, úgyhogy azt is váltani ezt az elemet. 

Most, 16 4-nél nagyobb. Szóval, úgy néz ki, szeretnénk beszúrni a 16 között, a 4 és a 23. Amíg mozog a rendezett részén a lista jobbról balra, 4 az első szám Láttuk, hogy a kisebb, mint a próbálunk beszúrni. Szóval, most már be a 16-ba az üres nyílásba, amely ne feledd, most már létrehozott mozgó elemek a rendezési rész felett ahogy már találkozott velük. 

Rendben van. Most már négy sorrendje elemet és két válogatott elemeket. Szóval, menjünk a 8 a rendezett rész. Nyolc kisebb, mint 42. Nyolc nem kevesebb, mint 23. És 8 nem kevesebb, mint 16. De 8 4-nél nagyobb. Szóval, szeretnénk beszúrni a 8 között, a 4 és a 16. És most már csak egy újabb elem maradt rendezni - a 15. Tizenöt kisebb, mint 42, Tizenöt nem kevesebb, mint 23. És 15 kisebb, mint 16. Azonban 15 nagyobb, mint 8. 

Szóval, itt van, ha azt akarjuk, hogy a végső helyezés. És mi történt. Jelenleg nincs több elem a rendezetlen rész, és a rendezett adag a helyes sorrendben. A számok sorrendben a legkisebbtől a legnagyobbig. Nos, vessünk egy pillantást néhány pszeudokód, amely leírja a lépéseket, már csak végre. 

On line 1, akkor láthatjuk, hogy mi kell megismételni az egyes elem a listán kivéve az első, hiszen az első elem a rendezetlen rész egyszerűen válik az első elem a rendezett rész. A vonalak 2 és 3, mi követi nyomon a jelenlegi helyét a rendezetlen rész. Element számát jelenti, mi jelenleg költözik a rendezett része, és j jelentése az index a rendezetlen rész. 

A 4-es vonal, mi iterációjával a válogatott rész jobbról balra. Azt akarjuk, hogy hagyja abba iterációjával egyszer az elemet balra aktuális pozíció kevesebb, mint az elemet próbálunk beszúrni. On line 5, mi változik az egyes elemek találkozunk egy hellyel jobbra. Így lesz egy üres hely beilleszteni, ha megtaláljuk az első elem kevesebb, mint az elem haladunk. On line 6, mi frissítjük ellentétes, hogy továbbra is mozogni balra a rendezett rész. Végül, 7. sor, mi az elem behelyezésekor a rendezett része a listán. 

Tudjuk, hogy nem baj, hogy helyezze be a helyére j, mert már át az elemet, hogy a használt, hogy ott egy hellyel jobbra. Ne feledje, hogy haladunk a válogatott rész jobbról balra, de haladunk át osztályozatlan részén balról jobbra. Rendben van. Nézzük most nézd meg, hogy mennyi ideig fut, algoritmus volt. Majd 1. tennünk a kérdést, hogy mennyi ideig tart, ez az algoritmus futtatásához a legrosszabb esetben. Emlékezzünk arra, hogy az általunk képviselt ez működési időt Big O jelölést. Annak érdekében, hogy rendezze a listát, azt kellett navigálhat az elemek rendezetlen rész, és az egyes elemei potenciálisan az összes elem a rendezett rész. Intuitíve, ez úgy hangzik, mint egy O (n ^ 2) működését. 

Keresi a mi pszeudokód, hogy van egy loop beágyazva egy hurok, amely valóban úgy hangzik, mint egy O (n ^ 2) működését. Azonban a rendezett része lista nem tartalmazza a teljes lista, egészen a végéig. Mégis, mi esetleg be egy új elemet legelején a rendezett rész minden iteráció a algoritmus, ami azt jelenti, hogy azt kell nézni minden egyes eleme jelenleg a rendezett rész. Tehát ez azt jelenti, hogy az egyik esetleg összehasonlítás a második elem, két összehasonlítást a harmadik elem, és így tovább. Így, a lépcsőfokok számát az összege az egész számok 1 és a hossza a jegyzék mínusz 1. Mi lehet képviseli ezt a összegzésben. 

Nem fogunk belemenni összegzések van, de kiderült, hogy ez a összegzési egyenlő n (n - 1) több mint 2, ami megegyezik n ^ 2/2 - n / 2. Amikor beszélünk, aszimptotikus futási, ez n ^ 2 kifejezést fogja uralni ezt a n kifejezést. Szóval, helyezés rendezés Big O (n ^ 2). Mi lenne, ha futott helyezés sort egy már rendezett listát. Ebben az esetben mi lenne egyszerűen felépíteni a rendezett rész balról jobbra. Szóval, akkor csak be kell a sorrendben az n lépéseket. 

Ez azt jelenti, hogy a beszúrási sort egy best-case teljesítése n, amit képviselnek, azzal Ω (n). És ez azt helyezés sort, Csak egy a sok algoritmusok tudjuk használni, hogy rendezni egy listát. A nevem Tommy, és ez CS50. [CS50.TV] Oh, csak nem tudja megállítani, hogy ha egyszer elindul. Ó, mi volt, hogy - >> Boom!