A beszúrásos rendezés (Insertion Sort) az egyik legegyszerűbb rendező algoritmus, melyet könnyű megérteni és implementálni. Ez az eljárás úgy működik, mint amikor kártyákat rendezünk a kezünkben. Képzeljük el, hogy a kártyák már rendezett sorban vannak a bal kézben, és egyesével vesszük a jobb kezünkben lévő kártyákat, hogy beilleszthessük őket a megfelelő helyre a bal kézben tartott rendezett sorban. A beszúrásos rendezés pont ilyen módon működik: egy iteráción belül kiválaszt egy elemet a bemeneti tömbből (ezt úgy tekinthetjük, mint a jobb kézben lévő kártyát) és beszúrja azt a már rendezett részben (a bal kézben lévő kártyák) a megfelelő helyre.
Működésének lépései
Az algoritmus általános lépései a következők:
- Feltételezzük, hogy a tömb első eleme már rendezett rész.
- A rendezetlen részből veszünk egy elemet.
- Ezt az elemet a megfelelő helyre beszúrjuk a rendezett részben.
- Ismételjük a folyamatot, amíg minden elemet át nem helyeztünk a rendezett részbe.
Ez a módszer hatékony kisebb adathalmazok rendezésekor, illetve szinte rendezett sorozatoknál, ahol minimális a mozgatás.
Algoritmus:
function Insertion-Sort-Steps($arr) {
for ($i = 1; $i -lt $arr.Length; $i++) {
$key = $arr[$i]
$j = $i - 1
# Move elements of $arr[0..$i-1], that are greater than $key, to one position ahead of their current position
while ($j -ge 0 -and $arr[$j] -gt $key) {
$arr[$j + 1] = $arr[$j]
$j = $j - 1
}
$arr[$j + 1] = $key
Write-Host "Lépés $i: $arr"
}
}
# Definiáljuk a tömböt
$arr = @(5, 2, 4, 6, 1, 3)
# Meghívjuk a rendező függvényt
Write-Host "Eredeti tömb: $arr"
Insertion-Sort-Steps $arr
Write-Host "Rendezett tömb: $arr"
Példák
Tegyük fel, hogy van egy tömbünk, amely az alábbi elemeket tartalmazza: [5, 2, 4, 6, 1, 3]. Az algoritmus lépésről lépésre való alkalmazásával kívánjuk megmutatni, hogyan rendeződik a tömb beszúrásos rendezés segítségével.
Első lépés:
Az első elem (5) már rendezettnek tekinthető.
Második lépés:
A 2 beszúrása előtt: [5, 2, 4, 6, 1, 3]
A 2 beszúrása után: [2, 5, 4, 6, 1, 3]
Harmadik lépés:
A 4 beszúrása előtt: [2, 5, 4, 6, 1, 3]
A 4 beszúrása után: [2, 4, 5, 6, 1, 3]
Ezt a folyamatot folytatva a többi elemmel, végül eljutunk a teljesen rendezett tömbhöz: [1, 2, 3, 4, 5, 6].
Részletesen:
Az alábbiakban bemutatom, hogyan rendeződik a [5, 2, 4, 6, 1, 3] tömb beszúrásos rendezés segítségével, lépésről lépésre:
- Lépés: [2, 5, 4, 6, 1, 3] – Az 5 és 2 pozíciójának megcserélése.
- Lépés: [2, 4, 5, 6, 1, 3] – A 4 beszúrása a megfelelő helyre, hogy 2 és 5 között legyen.
- Lépés: [2, 4, 5, 6, 1, 3] – A 6 már a helyén van, nincs változás.
- Lépés: [1, 2, 4, 5, 6, 3] – Az 1 beszúrása a tömb elejére.
- Lépés: [1, 2, 3, 4, 5, 6] – A 3 beszúrása a megfelelő helyre, hogy 2 és 4 között legyen.
Minden lépésben a kiemelt számot vesszük, és azt helyezzük a megfelelő pozícióba a már rendezett részsorozatban. Ez folytatódik, amíg az összes elemet a helyére nem rendezzük. Az eredményül kapott sorozat teljesen rendezett lesz.
Előnyök és hátrányok
Az előnye, hogy egyszerű az algoritmus és jól működik kisebb tömbökön, valamint közel rendezett adathalmazok esetén. A beszúrásos rendezés stabil rendezési eljárás, ami azt jelenti, hogy a megegyező kulcsú elemek eredeti sorrendje megmarad. A hátrány, hogy O(n^2) futási ideje van, ami alkalmatlanná teszi nagy adathalmazok hatékony rendezésére.
Leírás
A beszúrásos rendezés megértése és implementálása egy remek gyakorlat a programozás tanulásához, különösen kezdő programozók számára. Bár nem a leggyorsabb rendezési algoritmus nagy adathalmazok kezelésére, sok olyan helyzetben hasznos, ahol a rendezendő elemek száma korlátos vagy az adatok már részben rendezettek. Az algoritmus lényege, hogy iteratívan építi fel a rendezett tömböt, beszúrva minden új elemet a megfelelő helyre a már rendezett szekvenciában. Ez a fajta algoritmikus gondolkodásmód nemcsak a rendezési problémák megoldásában, hanem szélesebb körű programozási feladatok kezelésében is értékes tapasztalatot ad.