Summary of Beszúrásos rendezés (insertion sort)

## Bevezetés a Beszúrásos Rendezésbe A rendezés az informatikában az adatok egy adott szempont (például numerikus érték vagy ábécé sorrendje) szerinti elrendezését jelenti. Számos rendezési algoritmus létezik, amelyek különböző hatékonysággal és tulajdonságokkal rendelkeznek. A **beszúrásos rendezés** (angolul: Insertion Sort) egyike a legegyszerűbb rendezési algoritmusoknak, amelyet gyakran tanítanak a bevezető programozási kurzusokon. Egyszerűsége ellenére fontos szerepet játszik, különösen kis adathalmazok rendezésekor, vagy amikor az adatok már majdnem rendezett állapotban vannak. > A **rendezés** az adatok egy meghatározott sorrendbe (pl. növekvő vagy csökkenő) való elrendezésének folyamata. ## Működési Elv: A Kártyapakli Analógia A beszúrásos rendezés alapelve könnyen megérthető, ha elképzeljük, hogyan rendezünk egy pakli kártyát a kezünkben. Tegyük fel, hogy a bal kezünkben már van egy rendezett kártyasorozat, és a jobb kezünkben tartjuk a rendezetlen kártyákat. Egyenként vesszük ki a kártyákat a jobb kezünkből, és a bal kezünkben lévő rendezett sorozat megfelelő helyére illesztjük be. Minden új kártya beillesztésekor a bal kezünkben lévő rendezett sorozat egy elemmel bővül, miközben megőrzi rendezettségét. Ez az analógia tökéletesen leírja az algoritmus működését: az adathalmazt két részre osztjuk – egy már **rendezett részre** és egy **rendezetlen részre**. Kezdetben a rendezett rész csak az első elemet tartalmazza (mivel egyetlen elem mindig rendezettnek tekinthető), a többi elem pedig a rendezetlen részben van. Az algoritmus iteratívan kiválaszt egy elemet a rendezetlen részből, és beilleszti a megfelelő helyre a rendezett részbe, eltolva a nagyobb elemeket, hogy helyet csináljon neki. ### Az Algoritmus Részletes Leírása Tekintsünk egy $n$ elemű tömböt, amelyet rendezni szeretnénk. Az algoritmus a következő lépésekben működik: 1. **Kezdeti állapot:** Az első elem (index $0$) önmagában egy rendezett részlistát alkot. A többi $n-1$ elem a rendezetlen részlistát képezi. 2. **Iteráció:** Az algoritmus a második elemtől (index $1$) kezdve halad a tömb végéig (index $n-1$). Minden iterációban kiválasztja az aktuális elemet a rendezetlen részből. Ezt az elemet nevezzük „**kulcsnak**”. 3. **Beszúrás:** A kiválasztott kulcsot összehasonlítja a már rendezett részlista elemeivel, jobbról balra haladva. Ha a rendezett részlista egy eleme nagyobb, mint a kulcs, akkor azt az elemet egy pozícióval jobbra tolja. Ezt addig ismétli, amíg nem talál egy olyan elemet, amely kisebb vagy egyenlő, mint a kulcs, vagy amíg el nem éri a rendezett részlista elejét. 4. **Helyezés:** Miután megtalálta a megfelelő pozíciót, a kulcsot beilleszti oda. Ezzel a rendezett részlista egy elemmel bővül, és továbbra is rendezett marad. 5. **Folytatás:** Az algoritmus folytatódik a következő rendezetlen elemmel, amíg az összes elem be nem illesztésre került a rendezett részbe. Did you know that despite its relative inefficiency for large datasets, Insertion Sort is used as part of more complex sorting algorithms, like Timsort, which is the default sorting algorithm in Python and Java? ## Példa a Beszúrásos Rendezésre Nézzünk egy konkrét példát a $[5, 2, 4, 6, 1, 3]$ számsorozat rendezésére a beszúrásos rendezés segítségével. **Kezdeti tömb:** $[5, 2, 4, 6, 1, 3]$ 1. **lépés ($i = 1$, kulcs = $2$):** * A rendezett rész: $[5]$ * A kulcs $2$. Összehasonlítjuk az $5$-tel. * Mivel $2 < 5$, az $5$-öt jobbra toljuk. * A $2$-t beillesztjük az $5$ elé. * Tömb állapota: $[2, 5, 4, 6, 1, 3]$ 2. **lépés ($i = 2$, kulcs = $4$):** * A rendezett rész: $[2, 5]$ * A kulcs $4$. Összehasonlítjuk az $5$-tel. * Mivel $4 < 5$, az $5$-öt jobbra toljuk. * Összehasonlítjuk a $2$-vel. * Mivel $4 > 2$, a $4$-et beillesztjük a $2$ és az $5$ közé. * Tömb állapota: $[2, 4, 5, 6, 1, 3]$ 3. **lépés ($i = 3$, kulcs = $6$):** * A rendezett rész: $[2, 4, 5]$ * A kulcs $6$. Összehasonlítjuk az $5