Beszúrásos rendezés a PowerShellben

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:

1. Feltételezzük, hogy a tömb első eleme már rendezett rész.
2. A rendezetlen részből veszünk egy elemet.
3. Ezt az elemet a megfelelő helyre beszúrjuk a rendezett részben.
4. 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:

1. Lépés: [2, 5, 4, 6, 1, 3] – Az 5 és 2 pozíciójának megcserélése.
2. 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.
3. Lépés: [2, 4, 5, 6, 1, 3] – A 6 már a helyén van, nincs változás.
4. Lépés: [1, 2, 4, 5, 6, 3] – Az 1 beszúrása a tömb elejére.
5. 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.