Buborékrendezés (algoritmus)

A Programozás Wiki wikiből

A buborékrendezés egy egyszerű rendezési algoritmus. Nevét onnan kapta, hogy hasonlóan ahhoz, ahogy a pezsgőspohárban szállnak felfelé a buborékok, a rendezés során is minden egyes menetben a fennmaradó elemek közül a legnagyobbat "áramoltatjuk fel" a tömbszelet végére, tetejére. A rendezés során a tömb fennmaradó - még nem rendezett - részén végighaladva az egymás utáni szomszédos elemeket összehasonlítjuk, és ha szükséges megcseréljük őket, hogy közülük mindig a nagyobb helyezkedjen el feljebb; ezt a műveletet aztán a tömbön feljebb lépve addig ismételjük, amíg a fennmaradó rész végéhez nem érünk. A műveletsor végén a rendezetlen rész tetejére mindig a legnagyobb érték kerül majd fel, amelyet a következő menetben már nem veszünk figyelembe. A ciklust egészen addig ismételjük a fennmaradó - egyre kisebb - halmazon, amíg már csak egyetlen elem marad ebben, amely ebben az esetben a halmaz legkisebb eleme lesz, miközben a tömb fennmaradó része az összes nála nagyobb elemet fogja tartalmazni, növekvő sorrendben.

Az algoritmus műveletigénye a tömb méretének négyzetével arányos, ezért nagy tömböknél nem javasolt a használata, mert rendkívül lassú futáshoz vezet. Ilyen esetekre a gyorsrendezés vagy az összefésülő rendezés használata ajánlott. A minimumkiválasztásos és a beszúrásos rendezések általában hatékonyabbak a buborékrendezésnél.

C példa:

   void bubble( int [] arr, int size ) {
      int i;
      int j;
      int tmp;
      for (i=size-1; 0<i; --i) {
         for (j=0; j < i; ++j) {
            if (a[j]>a[j+1]) {
               // csere
               tmp=a[j];
               a[j]=a[j+1];
               a[j+1]=tmp;
            }
         }
      }
   }

Az algoritmus javítható, ha megfigyeljük, hogy a külső ciklusnak csak akkor érdemes tovább futnia, ha a belső ciklusban volt csere. Erre bevezethetünk egy logikai változót, így a javított algoritmus a következőképpen néz ki:

   void bubble( int [] arr, int size ) {
      int i;
      int j;
      int tmp;
      bool csere=true;
      for (i=size-1; 0<i && csere; --i) {
         csere=false; 
         for (j=0; j < i; ++j) {
            if (a[j]>a[j+1]) {
               // csere
               tmp=a[j];
               a[j]=a[j+1];
               a[j+1]=tmp;
               csere=true; // ha volt csere, a változót igazra állítjuk
            }
         }
      }
   }

Egy másik javítási módszer lehet, ha megjegyezzük egy adott ciklusban az utolsó cserélt elem pozícióját, és legközelebb már csak addig megyünk a ciklusban. Erre a célra vezessük be az uj_i nevű változót! A kapott algoritmus:

   void bubble( int [] arr, int size ) {
      int tmp;
      int i = size - 1;
      int uj_i;
      while (i >= 1) {
          uj_i = 0;
          for (int j = 0; j < i; j++) {
            if (a[j] > a[j + 1]) {
               // csere
               tmp = a[j];
               a[j] = a[j + 1];
               a[j + 1] = tmp;
               uj_i = j;
             }
          }
          i = uj_i;
       }   
   }

Látható, hogy a kódban az i változó jelzi azt, hogy meddig megyünk, és minden ciklus végén frissítjük ezt a változót az uj_i értékével.