Buborékrendezés

Buborékrendezés
A buborékrendezésre egy példa
Kategória	rendezési algoritmus
Adatstruktúra	tömb
Legrosszabb időbonyolultság	$O(n^2)$
Legjobb időbonyolultság	$O(n)$
Átlagos idő bonyolultság	$O(n^2)$
Legrosszabb tár bonyolultság	$O(1)$
Optimális	nem

Buborékrendezésre egy példa. A piros négyzetek jelzik az épp összehasonlított elemeket, a fekete jelzi azokat az elemeket, amik már a rendezés szerinti végső helyükön vannak.

A buborékrendezés (angolul: Bubble sort) egy naiv algoritmus, amellyel egy véges (nem feltétlenül numerikus) sorozat – vagy számítástechnikai szóhasználattal élve egy tömb – elemei sorba rendezhetők [(n-1)n]/2 összehasonlítás elvégzésével, ahol n a sorozat elemeinek számát jelenti. Mivel az algoritmus nem túl hatékony, a gyakorlatban szinte egyáltalán nem, inkább csak az algoritmuselmélet oktatása során használják.

Az algoritmus

Az algoritmus alkalmazásának feltétele hogy a sorozat elemeihez létezzen egy rendezési reláció. Az algoritmus újra és újra végigiterál a listán, összehasonlítja a lista szomszédos elemeit, és ha azok az elvárt rendezéshez képest fordítva vannak, akkor megcseréli őket. Első menetben a lista elejéről indul és a végéig megy. Ennek az első menetnek az eredményeként a legnagyobb elem (mint egy buborék) felszáll a lista végére. Így a következő menetben már elegendő az utolsó előtti elemig elvégezni a szomszédos elemek összehasonlítását és cseréjét. Az ezután következő menetben a lista utolsó két eleme lesz a helyén és így tovább... Az algoritmus két egymásba ágyazott ciklusból áll. A tömb első elemének indexe 0, elemeinek száma pedig n. Az elemek itt számok, és a reláció a > (nagyobb).

   CIKLUS i = n-1 TŐL 1 IG {
       CIKLUS j = 0 TÓL i-1 IG {
           HA TOMB[j] > TOMB[j+1] AKKOR {
               CSERÉLD FEL ŐKET: TOMB[j], TOMB[j+1]
           }
       }
   }

A futás befejezése után a tömb 0-ás indexű eleme lesz a legkisebb és az n-1-es indexű a legnagyobb.

A buborékrendezés illusztrálása. Az (x, y) pont jelentése: az y érték a tömb x-edik eleme.

Az algoritmus onnan kapta a nevét, hogy először a legnagyobb elem „száll fel” a tömb utolsó helyére, utána a második legnagyobb az azt követő helyre, és így tovább, mint ahogy a buborékok szállnak felfelé egy pohárban.

Források

• Angster Erzsébet: Programozás Tankönyv I. (4KÖR Bt., 1999)
• Rónyai Lajos – Ivanyos Gábor – Szabó Réka: Algoritmusok (Typotex, 1999)
• egyéb rendezések:
  • Thomas H. Cormen – Charles E. Leiserson – Ronald L. Rivest: Algoritmusok (Műszaki Könyvkiadó, 2003)

Kapcsolódó szócikkek

• Rendezés (programozás)
• Koktélrendezés
• Fésűs rendezés
• Gyorsrendezés
• Kupacrendezés
• Beszúrásos rendezés

További információk

• A buborékrendezés szemléltetése csángó néptánccal. YouTube
• Programozni egyszerű! - Buborékrendezés Archiválva 2011. szeptember 24-i dátummal a Wayback Machine-ben