Buborékrendezés

A Wikipédiából, a szabad enciklopédiából
Buborékrendezésre egy példa

A buborékrendezés (angolul: Bubble sort) egy egyszerű 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[szerkesztés | forrásszöveg szerkesztése]

Az algoritmus alkalmazásának feltétele hogy a sorozat elemeihez létezzen egy rendezési reláció.

Az algoritmus két egymásba ágyazott ciklusból áll. A tömb első elemének indexe az 1, elemeinek száma pedig n. Az elemek itt számok, és a reláció a > (nagyobb).

   CIKLUS i = n TŐL 2 IG {
       CIKLUS j = 1 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 1-es indexű eleme lesz a legkisebb és az n indexű a legnagyobb.

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[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]

További információk[szerkesztés | forrásszöveg szerkesztése]