Több alapvető algoritmus létezik a tömb rendezési problémájának megoldására. Az egyik leghíresebb közülük a beillesztési rendezés. Letisztultsága és egyszerűsége, de alacsony hatékonysága miatt ezt a módszert elsősorban a programozás oktatásában alkalmazzák. Lehetővé teszi az alapvető rendezési mechanizmusok megértését.
Az algoritmus leírása
A beillesztési rendezési algoritmus lényege, hogy a kezdeti tömbön belül egy megfelelően rendezett szegmens jön létre. Minden elemet egyenként összehasonlítanak a bejelölt résszel, és beillesztik a megfelelő helyre. Így az összes elem iterációja után a megfelelő sorrendbe kerülnek.
Az elemek kijelölésének sorrendje tetszőleges lehet, tetszőlegesen vagy valamilyen algoritmus szerint választhatók ki. Leggyakrabban a szekvenciális felsorolást a tömb elejétől használjuk, ahol egy rendezett szegmens jön létre.
A rendezés kezdete így nézhet ki:
- Vegyük a tömb első elemét.
- Mivel nincs mihez hasonlítani, vegye magát az elemet a sorrendbensorozat.
- Ugrás a második elemre.
- Hasonlítsa össze az elsővel a rendezési szabály alapján.
- Ha szükséges, cserélje fel az elemeket helyeken.
- Vegye az első két elemet rendezett sorozatnak.
- Ugrás a harmadik elemre.
- Hasonlítsa össze a másodikkal, szükség esetén cserélje ki.
- Ha a csere megtörtént, hasonlítsa össze az elsővel.
- Vegyünk három elemet rendezett sorozatként.
És így tovább az eredeti tömb végéig.
Valós beillesztési rendezés
Az érthetőség kedvéért érdemes példát hozni arra, hogyan használják ezt a válogatási mechanizmust a mindennapi életben.
Vegyünk például egy pénztárcát. Száz-, ötszáz- és ezerdolláros bankjegyek hevernek zavartan a bankjegyrekeszben. Ez egy rendetlenség, egy ilyen kavargóban nehéz azonnal megtalálni a megfelelő papírt. A bankjegyek tömbjét rendezni kell.
A legelső egy 1000 rubeles bankjegy, közvetlenül utána pedig 100. Vegyünk egy százast, és elé helyezzük. A harmadik a sorban 500 rubel, a jogos hely száz és ezer között van.
Ugyanígy rendezzük a kapott kártyákat a „bolond” kijátszásakor, hogy könnyebben eligazodjunk bennük.
Operátorok és segédfunkciók
A beillesztési rendezési módszer bemenetként egy kezdeti rendezendő tömböt, egy összehasonlító függvényt, és ha szükséges, egy függvényt vesz fel, amely meghatározza az elemek felsorolásának szabályát. Leggyakrabban helyette használjákszabályos ciklus utasítás.
Az első elem maga egy rendezett halmaz, így az összehasonlítás a másodiktól kezdődik.
Az algoritmus gyakran használ segédfunkciót két érték cseréjéhez (csere). Egy további ideiglenes változót használ, amely memóriát fogyaszt, és egy kicsit lelassítja a kódot.
Egy másik lehetőség az elemek egy csoportjának tömeges eltolása, majd az aktuális elem beszúrása a szabad helyre. Ebben az esetben a következő elemre való áttérés akkor történik, amikor az összehasonlítás pozitív eredményt adott, ami a helyes sorrendet jelzi.
Megvalósítási példák
A konkrét megvalósítás nagymértékben függ a használt programozási nyelvtől, annak szintaxisától és szerkezetétől.
Classic C megvalósítás ideiglenes változó használatával az értékek cseréjéhez:
int i, j, temp; for (i=1; i =0; j--) { if (array[j] < temp) break; tömb[j + 1]=tömb[j]; tömb[j]=hőmérséklet; } }
PHP megvalósítás:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Itt először minden olyan elem, amely nem egyezik a rendezési feltétellel, jobbra tolódik, majd az aktuális elem bekerül a szabad helyre.
Java kód a while ciklus használatával:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[előzőKulcs]; arr[prevKey]=currElem; prevKey--; } } }
A kód általános jelentése változatlan marad: a tömb minden elemét szekvenciálisan összehasonlítjuk az előzőekkel, és szükség esetén felcseréljük velük.
Becsült működési idő
Nyilvánvalóan a legjobb esetben az algoritmus bemenete egy már megfelelő módon rendezett tömb lesz. Ebben a helyzetben az algoritmusnak egyszerűen ellenőriznie kell az egyes elemeket, hogy megbizonyosodjon arról, hogy a megfelelő helyen van, anélkül, hogy cseréket végezne. Így a futási idő közvetlenül függ az eredeti O(n) tömb hosszától.
A legrosszabb eset bemenete egy fordított sorrendben rendezett tömb. Ehhez nagyszámú permutációra lesz szükség, a futásidejű függvény az elemek számának négyzetétől függ.
A teljesen rendezetlen tömb permutációinak pontos száma a következő képlettel számítható ki:
n(n-1)/2
ahol n az eredeti tömb hossza. Így 4950 permutációra lenne szükség 100 elem megfelelő sorrendbe rendezéséhez.
A beillesztési módszer nagyon hatékony kis vagy részben rendezett tömbök rendezésére. A számítások bonyolultsága miatt azonban nem ajánlott mindenhol alkalmazni.
Az algoritmust sok más bonyolultabb rendezési módszer segédeszközeként használják.
Egyenlő értékek rendezése
A beillesztési algoritmus az úgynevezett stabil rendezések közé tartozik. Azt jelenti,hogy nem cseréli fel az azonos elemeket, hanem megőrzi azok eredeti sorrendjét. A stabilitási index sok esetben fontos a helyes sorrendhez.
A fenti egy nagyszerű vizuális példa a beillesztésre egy táncban.
