Buborékrendezés
A Wikipédiából, a szabad lexikonból.
A buborékrendezé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 [(n-1)n]/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.
Tartalomjegyzék |
[szerkesztés] Az algoritmus
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[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.
[szerkesztés] Érdekesség
Két változó értékének felcseréléséhez általában segédváltozót vezetnek be, de a változók típusától függően más megoldások is elképzelhetők.
Lássuk először a hagyományos módszert, azaz az a és b változó tartalmának felcserélését az s segédváltozó felhasználásával:
s = a
a = b
b = s
Ha a változók típusára értelmezett a kizáró vagy (exclusive or = xor) művelet (például logikai típusok, egész számok), szintén megoldáshoz jutunk, ha segédváltozó használata helyett felhasználjuk a művelet azon tulajdonságát, hogy: (a xor b) xor b = a:
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"
(Ha a használt típusra nem értelmezett a xor, akkor is használható, például úgy hogy az adatot részekre bontva (pl. byte-okra) cast-oljuk egy megfelelő (pl. char) típusra, majd ezeken végezzük el a xor-t.)
[szerkesztés] C példaprogram
Itt a tömb 0-tól lett indexelve, ezért van eltérés a ciklusokban.
#include <stdio.h>
#define ESZ 7
int main (void)
{
int i, j, s;
int tomb[ESZ] = {23, 12, 100, 6, 55, 24, 2};
for (i=ESZ-2; i>=0; i--) {
for (j=0; j<=i; j++) {
if (tomb[j] > tomb[j+1]) {
s = tomb[j];
tomb[j] = tomb[j+1];
tomb[j+1] = s;
}
}
}
printf("A rendezett tomb:\n\n");
for (i=0; i<ESZ; i++) printf("%d ", tomb[i]);
return 0;
}
[szerkesztés] Pascal példaprogram
program buborekrendezes;
uses crt;
{deklaráció}
var
i,j,n,s:integer;
tomb:array[1..256] of integer;
b:char;
begin
clrscr;
n:=0;
b:='i';
{beolvasás}
while b<>'n' do
begin
n:=n+1;
writeln('kérem a számot!');
readln(tomb[n]);
writeln('van még szám?(i/n)');
readln(b);
end;
{rendezés}
for i:=n-1 downto 1 do
begin
for j:=1 to i do
begin
if tomb[j]>tomb[j+1]then
begin
s:=tomb[j];
tomb[j]:=tomb[j+1];
tomb[j+1]:=s;
end;
end;
end;
{kiiratás}
writeln;
write('A számok sorrendben:');
for i:=1 to n do
begin
write(tomb[i],' ');
end;
readln;
end.
[szerkesztés] 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.


Based on work by