[Zenelejátszási] 

DOUG LLOYD: Szóval beillesztés sort egy másik algoritmust tudjuk használni, hogy rendezni egy tömb. Az ötlet mögött ez az algoritmus hogy létrejöjjön a rendezett tömbben a helyén, a változó elemek ki az út, ahogy megy, hogy helyet csináljon. Ez kicsit más a kijelölés ilyen vagy buborék rendezés, például, ahol mi kiigazításáról helyeken, ahol tesszük swap. 

Ebben az esetben mi vagyunk valójában Ennek a csúszó elemek vége, az útból. Hogyan működik ez az algoritmus dolgozni pszeudokódja? Nos nézzük csak önkényesen mondani, hogy a első eleme a tömb rendezve. Építünk a helyére. 

Mi fog menni egyik eleme egy időben, és építeni, és így az első dolog, amit látni egy egyik eleme tömb. És a meghatározás szerint az egyik elem tömb rendezve. 

Akkor ismételje meg ezt a folyamatot until-- fogjuk ismételni a következő eljárás amíg az összes elemet vannak rendezve. Nézd meg a következő osztályozás nélküli elem és helyezze be a rendezett része, eltolásával a szükséges számú elemek az útból. Remélhetőleg ez a vizualizáció segít, hogy pontosan mi folyik a behelyezés sort. 

Szóval megint itt van a teljes válogatás nélkül tömb, az összes elem pirossal jelzett. És kövessük a lépéseit a pszeudokódja. Az első dolog, amit csinálunk, az hívjuk a első eleme a tömb, válogatni. Szóval mi csak akarsz mondani öt, te most válogatni. 

Akkor nézzük a következő válogatás nélkül a tömb elemének és szeretnénk beszúrni, hogy a rendezve része, eltolásával elemek fölött. Tehát két a következő szétválogatás nélkül elem a tömb. Nyilvánvaló tartozik előtt öt, akkor mi csinálunk A fajta tartsa két félre egy pillanatra, váltás öt fölött, majd helyezze be a két öt előtt, hol kell menni. És most azt mondhatjuk, hogy a két rendezve. 

Tehát mint látható, most már csak eddig nézett a két tömb elemei. Még nem nézett pihenni egyáltalán, de mi már kapott e két elem sorolva módja a változó mechanizmus. 

Tehát ismételjük meg a folyamatot újra. Nézd meg a következő szétválogatás nélkül eleme, hogy az egyik. Nézzük meg, hogy félre egy pillanatra, váltás mindent ért, és egyik hová kell mennie. 

Ismét mindig, most már mindig csak nézett egy, kettő, öt. Nem tudjuk, mi más jön, de már válogatni a három elemet. 

Következő szétválogatott elem három, úgyhogy majd tegye félre. Majd álljak át, amit mi kell, hogy melyik, ezúttal nem minden, mint az előző Két esetben ez csak öt. És akkor maradok három, a kettő között, és az öt. 

Hat a következő szétválogatás nélkül elem a tömbben. És valóban hat nagyobb, mint öt, így mi nem is kell semmilyen csere. Mi is csak irányt hat közvetlenül a a végén a rendezve rész. 

Végül négy a Utolsó szétválogatott elem. Szóval majd tegye félre, álljak át Az elemek meg kell álljak át, majd fel négy, ahova tartozik. És most nézd, mi már egyfajta minden elemét. Figyeljük meg a beillesztés sort, nem volt hogy menjen vissza oda az egész tömböt. Mi csak akkor ment át a tömböt Egy időben, és toltuk a dolgokat hogy mi lenne a már felmerült, annak érdekében, hogy helyet csináljon az új elemeket. 

Szóval mi a legrosszabb esetben forgatókönyv a beillesztés sort? A legrosszabb esetben, a tömb fordított sorrendben. Meg kell váltani az egyes elemek n n-ig pozíciókat, minden egyes alkalommal, amikor a beszúrási. Ez nagyon sok a változó. 

A legjobb esetben, a tömb tökéletesen rendezve. És valami, mint mi történt öt és hat a példában, ahol tudnánk csapáson azt anélkül, hogy ezt bármilyen változó, mi lenne alapvetően csinálni. 

Ha tudod képzelni, hogy mi tömb egyike volt a hat, mi lenne elindul a nyilvánító egy rendezve. Két után jön valaki így tudjuk csak azt mondják, OK, jól egy-két helyre nem kerül. Három után jön két igen, OK, egy és kettő és három sorrendje. 

Nem vagyunk bármilyen csereügyletek vagyunk csak mozog ez az önkényes vonal között rendezett és rendezetlen, ahogy haladunk. Olyan hatékonyan, mint mi a példában, fordult elemek kék, ahogy haladunk tovább. Szóval mi a legrosszabb esetben runtime, akkor? Ne feledd, ha meg kell váltani az egyes Az n elem esetleg n pozíciók, remélhetőleg, hogy megadja neked egy ötlet, hogy a legrosszabb esetben üzemidő Big O n négyzeten. 

Ha a tömb tökéletesen válogatni, minden, amit meg kell csinálni A nézd meg minden egyes elem egyszer, és akkor kész. Tehát a legjobb esetben, ez az omega n. 

Én Doug Lloyd. Ez CS50.