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.