# Buborékrendezés: Egy Alapvető Rendezési Algoritmus Üdvözöllek! Ebben a tananyagban a **buborékrendezés** nevű algoritmust fogjuk részletesen megismerni. Ez egyike a legegyszerűbb rendezési algoritmusoknak, és bár a gyakorlatban ritkán használják nagy adathalmazok esetén a hatékonysága miatt, kiválóan alkalmas az algoritmusok működési elvének megértésére. Készen állsz, hogy elmerülj a rendezés világában? ## Mi az a buborékrendezés? > A **buborékrendezés** (angolul: bubble sort) egy egyszerű rendezési algoritmus, amely ismételten végigmegy egy listán, összehasonlítja a szomszédos elemeket, és felcseréli őket, ha rossz sorrendben vannak. Az algoritmus nevét onnan kapta, hogy a nagyobb (vagy kisebb, a rendezés irányától függően) elemek fokozatosan „felbuborékolnak” a lista végére, míg a kisebbek „lesüllyednek” az elejére. Ez az algoritmus különösen intuitív, hiszen a működését könnyű elképzelni. Képzeld el, hogy buborékok emelkednek fel egy vízoszlopban: a legkönnyebbek (legkisebbek) maradnak lent, míg a nehezebbek (nagyobbak) felülre jutnak. A rendezés során is valami hasonló történik az elemekkel. Did you know, hogy a buborékrendezés az egyik legrégebben ismert rendezési algoritmusok egyike, és gyakran használják bevezető példaként a programozás oktatásában az egyszerűsége miatt? ## Működési elv A buborékrendezés alapelve rendkívül egyszerű: a lista elemeit páronként összehasonlítja, és ha a sorrendjük nem megfelelő, felcseréli őket. Ezt a folyamatot addig ismétli, amíg egy teljes menet során nem történik csere, ami azt jelzi, hogy a lista rendezetté vált. Tekintsünk egy növekvő sorrendbe rendezendő számokból álló listát. Az algoritmus a következőképpen működik: ### 1. Első menet Az algoritmus a lista elejétől indulva összehasonlítja az első és a második elemet. Ha az első nagyobb, mint a második, felcseréli őket. Ezután összehasonlítja a második és a harmadik elemet, és szükség esetén felcseréli őket. Ezt a folyamatot egészen a lista végéig folytatja. Az első menet végére a legnagyobb elem garantáltan a lista utolsó pozíciójára kerül. ### 2. További menetek Az algoritmus megismétli az előző lépést, de minden egyes menetben eggyel kevesebb elemet kell vizsgálni, mivel a lista végén lévő elemek már a helyükön vannak. Például a második menetben a lista utolsó eleme már rendezettnek tekinthető, így csak az első $n-1$ elemet kell vizsgálni, ahol $n$ a lista elemeinek száma. ### 3. Leállítási feltétel Az algoritmus akkor áll le, ha egy teljes menet során nem történt egyetlen csere sem. Ez azt jelenti, hogy a lista már rendezett, és minden elem a megfelelő helyen van. ## Példa a buborékrendezésre Vegyünk egy rendezetlen listát: $[5, 1, 4, 2, 8]$ **1. menet:** * $[5, 1, 4, 2, 8]$ $\rightarrow$ Összehasonlítjuk az 5-öt és az 1-et. $5 > 1$, tehát csere: $[1, 5, 4, 2, 8]$ * $[1, 5, 4, 2, 8]$ $\rightarrow$ Összehasonlítjuk az 5-öt és a 4-et. $5 > 4$, tehát csere: $[1, 4, 5, 2, 8]$ * $[1, 4, 5, 2, 8]$ $\rightarrow$ Összehasonlítjuk az 5-öt és a 2-t. $5 > 2$, tehát csere: $[1, 4, 2, 5, 8]$ * $[1, 4, 2, 5, 8]$ $\rightarrow$ Összehasonlítjuk az 5-öt és a 8-at. $5 < 8$, nincs csere. Az első menet végén a legnagyobb elem (8) a helyére került: $[1, 4, 2, 5, 8]$ **2. menet:** (Az utolsó elem (8) már a helyén van, így csak az első 4 elemet vizsgáljuk) * $[1, 4, 2, 5, 8]$ $\rightarrow$ Összehasonlítjuk az 1-et és a 4-et. $1 < 4$, nincs csere. * $[1, 4, 2, 5, 8]$ $\rightarrow$ Összehasonlítjuk a 4-et és a 2-t. $4 > 2$, tehát csere: $[1, 2, 4, 5, 8]$ * $[1, 2, 4, 5, 8]$ $\rightarrow$ Összehasonlítjuk a 4-et és az 5-öt. $4 < 5$, nincs csere. A második menet végén a második legnagyobb elem (5) a helyére került: $[1, 2, 4, 5, 8]$ **3. menet:** (Az utolsó két elem (5, 8) már a helyén van, így csak az első 3 elemet vizsgáljuk) * $[1, 2, 4, 5, 8]$ $\rightarrow$ Összehasonlítjuk az 1-et és a 2-t. $1 < 2$, nincs csere. * $[1, 2, 4, 5, 8]$ $\rightarrow$ Összehasonlítjuk a 2-t és a 4-et. $2 < 4$, nincs csere. A harma