Buborékrendezés
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.
Tartalomjegyzék |
Az algoritmus [szerkesztés]
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.
Lásd még [szerkesztés]
Források [szerkesztés]
- 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)
