Beszúró rendezés

Többféleképpen lehet rendezni. A minimumkiválasztásos rendezés futása során a résztömb a tömb elején rendezetté válik, de a végén levő résztömb nem. A minimumkiválasztásos rendezés a rendezetlen résztömböt vizsgálja meg a következő elem kiválasztásához, amit majd beszúr a már rendezett résztömbbe.

A rendezést másképpen is megközelíthetjük. Képzeld el, hogy kártyázol. Kártyákat tartasz a kezedben, és ezek a kártyák sorba vannak rendezve. Az osztó ad neked pontosan egy új kártyát. Be kell illesztened azt a meglévő kártyáid közé úgy, hogy azok továbbra is rendezett sorrendben legyenek. A minimumkiválasztásos rendezés esetén a rendezett résztömbhöz hozzáadandó új elem sohasem kisebb, mint a rendezett résztömb többi eleme. De a mi kártyás példánkban az új kártya kisebb lehet a kezedben levő kártyák némelyikénél, úgyhogy végignézed a kártyáidat, összehasonlítod az új kártyával, amíg meg nem találod az új kártya helyét. Beilleszted az új kártyát a megfelelő helyre, és újból teljesen rendezett kártyacsomagod van. Ekkor az osztó egy újabb kártyát nyújt át, és te megismétled a fenti eljárást. Újabb és újabb kártyákat kapsz, amíg az osztó végül abba nem hagyja.

Ez a beszúró rendezés alapgondolata. Vizsgáld végig a tömb elemeit az 1-es indextől kezdve. Minden új pozíció olyan, mint az osztó által átnyújtott kártya, be kell illesztened a rendezett résztömb megfelelő helyére az adott pozíciótól balra. Megjelenítettük az egyes lépéseket: (Feliratok szövege: 1. Beszúró rendezés (Insertion sort) 2. Nyomd meg a 'Next step' gombot a kezdéshez (Press 'Next step'...) 3. Vizsgáld meg, és tárold az 1(2,3,4,5,6,7). indexű helyen található kártyát (Inspect and sort...) 4. Mozgasd a kártyát jobbra, hogy megnyisd a megfelelő helyet a tárolt kártyának (Move cards...) 5. Helyezd a tárolt kártyát a megfelelő végleges helyére (Place the stored card...) 6. A gomb felirata: Következő lépés)

Ha tömbökben gondolkodunk, tegyük fel, hogy a 0-tól az $5$‍. indexig az elemek már sorba vannak rendezve, és a jelenleg 6. indexen található elemet szeretnénk beilleszteni ebbe a rendezett résztömbbe úgy, hogy ezután a 0.-tól a $6$‍. indexig található elemek rendezettek legyenek. Így kezdjük:

Amikor végeztünk, a résztömb így néz ki:

A 6. pozíción található elemet úgy szúrjuk be a tőle balra levő résztömbbe, hogy ismételten összehasonlítjuk a tőle balra levő elemekkel, jobbról balra haladva. Hívjuk a 6. pozíción levő elemet kulcsnak. Minden alkalommal, amikor azt látjuk, hogy a kulcs kisebb, mint a tőle balra található elem, akkor azt az elemet eggyel jobbra csúsztatjuk, mert tudjuk, hogy a kulcsot ettől az elemtől balra kell elhelyezni. Két dolgot kell tennünk ahhoz, hogy ez az elgondolás működőképes legyen: szükségünk lesz egy csúsztatásra (slide), ami egy elemet eggyel jobbra csúsztat, és el kell menteni a kulcs értékét egy külön helyre (azért, hogy nehogy felülíródjon a tőle jobbra található elemmel). A mi példánkban tegyük a 6. indexű elemet egy key nevű változóba:

Most összehasonlítjuk a keyt az 5. pozíción levő elemmel. Azt látjuk, hogy key (5) kisebb, mint az 5. pozíción levő elem (13), ezért ezt az elemet átcsúsztatjuk a 6. pozícióra:

Figyeld meg, hogy a csúsztatás művelet csak annyit csinál, hogy egy elemet egy pozícióval jobbra másol. Ezután a key-t a 4. pozíció elemével hasonlítjuk össze. Azt látjuk, hogy key (5) kisebb, mint a 4. pozíción levő érték (10), és ezt az elemet is arrébb csúsztatjuk:

Ezután összehasonlítjuk key-t a 3. pozíción levő elemmel, és ezt az elemet is arrébb csúsztatjuk:

ugyanez történik a 2. pozíción:

Most elérkeztünk az 1. pozícióhoz, ahol a 3 található. Ez az elem kisebb, mint key, úgyhogy ezt nem csúsztatjuk arrébb. Ehelyett elhelyezzük key-t közvetlenül a vizsgált elem jobb oldalán (azaz a 2. pozícióba), amit épp ezt megelőzően csúsztattunk jobbra. Ennek eredményeképpen a résztömb 0-6-ig rendezett lesz:

A beszúró rendezés sorozatosan beszúr egy elemet a már rendezett résztömbbe. Azt mondhatjuk, hogy a kiinduláskor a 0 indexű elemet tartalmazó résztömb rendezett, mivel csak egy elemet tartalmaz, és egy elem önmagához képest mindig rendezett sorrendben van. Menjünk végig egy példán! Itt van a kezdeti tömbünk:

Mivel a 0 indexű elemet tartalmazó résztömb a kiinduló rendezett résztömbünk, az első kulcs az 1-es indexű elem lesz. (A rendezett résztömböt pirossal, a kulcsot sárgával, és a még rendezésre váró résztömböt kékkel jelöljük.) Beszúrjuk a kulcsot a balra látható rendezett résztömbbe:

Most a rendezett résztömb 0-tól 1-ig tart, és az új kulcs a 2-es indexű elem. Beillesztjük a tőle balra található rendezett résztömbbe:

És így tovább, egyenként megvizsgáljuk a tömb elemeit kulcsként, és behelyezzük a megfelelő pozícióba a tőle balra levő rendezett résztömbbe:

Miután a jobb szélső elemet a tömbben a helyére tettük, az egész tömb rendezett lett:

A fenti példában van egy-két dolog, amit érdemes közelebbről megvizsgálni: amikor a beillesztendő kulcs kisebb az összes, tőle balra található elemnél (például amikor a 2-t illetve 3-at szúrtuk be), valamint amikor nagyobb, vagy egyenlő a tőle balra levő összes elemnél (mint amikor a 13-at vittük a helyére). Az első esetben a kulcshoz képest balra eső résztömb minden eleme eggyel jobbra csúszik, és meg kell állnunk, amikor kifogytunk a tömb-elemekből. A második esetben azt tapasztaljuk az első összehasonlítás után, hogy a kulcs már a megfelelő helyen van a tőle balra levő összes elemhez képest, egy elemet se kell mozgatni, a kulcsot visszatesszük oda, ahonnan indult.

A beszúró rendezés legfontosabb lépése az, amikor helyet csinálunk a key változóban tárolt aktuális elem tömbbe való beillesztéséhez. Ahogy a fentiekben végigkövettük, végigmegyünk a key eredeti pozíciójától balra levő résztömb elemein jobbról balra, és minden key-nél nagyobb elemet eggyel jobbra csúsztatunk. Amint találunk egy key-nél kisebb, vagy key-vel egyenlő elemet, abbahagyjuk a csúsztatást és az adott elemtől jobbra levő, éppen szabaddá vált helyre másoljuk át key értékét. (Persze az a pozíció nem igazán üres, de az ott lévő elemet már jobbra csúsztattuk.) Az alábbi ábra illusztrálja, mi történik:

Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tanmenetfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.