A buborék rendezés 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 ^*/2 összehasonlítás elvégzésével, ahol n a sorozat elemeinek számát jelenti. Mivel a lépések száma négyzetesen nő az elemszámmal, ezért ez az algoritmus igen lassú, alkalmazása csak kis méretű tömbök rendezésére javasolt.

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-1 TŐL 1 IG { CIKLUS j = 1 TŐL i IG { HA TOMB> TOMB[j+1 AKKOR { CSERÉLD FEL ŐKET: TOMBTOMB[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.

Érdekesség:
Sokan úgy tudják/tanítják, hogy két változó értékének felcseréléséhez mindenképpen szükséges legalább egy segédváltozó, pedig ez koránt sem igaz. Lássuk először a hagyományos módszert:

Az a és b változó tartalmát cseréljük ki az s segédváltozó felhasználásával: s = a a = b b = s Szintén megoldáshoz jutunk, ha egy segédváltozó használata helyett felhasználjuk a "kizáró vagy" (exclusive or = xor) logikai művelet azon tulajdonságát, hogy: (a xor b) xor b = a. A xor-os csere így néz ki: a = a xor b b = a xor b //most "b"-be került az "a" tartalma a = a xor b //végül az "a"-ba az eredeti "b"

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.

Algoritmusok

Bubble sort ترتيب الفقاعات Bubblesort Ordenamiento de burbuja Kuplalajittelu Tri à bulles מיון בועות Bóluröðun Bubble sort バブルソート Burbulo rūšiavimo algoritmas Bubblesort Sortowanie bąbelkowe Bubble sort Сортировка пузырьком Bublinkové triedenie Bubble sort Сортування стандартним обміном 冒泡排序