: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > sortowanie >

S O R T O W A N I E   B Ą B E L K O W E

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30

 
       

Poniższy algorytm służy do sortowania liczb tablicy w porządku niemalejącym. Poszczególne liczby tablicy kolejno są przemieszczane we właściwe jej miejsca - najpierw największa, następnie największa z pozostałych, itd. Gdyby ustawić tablicę pionowo umieszczając jej pierwszy element na dole zaś ostatni na górze, to podczas pracy algorytmu liczby "unosiłyby" się ku górze niczym bąbelki w cieczy, co tłumaczy nazwę algorytmu sortowanie bąbelkowe

Mówimy, że tablica liczb posortowana jest w sposób niemalejący, gdy każdy element tablicy oprócz ostatniego jest nie większy od elementu następnego.
Analogicznie mówimy, że tablica liczb jest posortowana w sposób nierosnący, gdy każdy element tablicy oprócz ostatniego jest nie mniejszy od elementu następnego.
Niech dana będzie tablica Tab zawierająca N liczb. Pierwsze dwie liczby tablicy możemy za sobą porównać a następnie większą z nich umieścić na drugim miejscu tablicy, mniejszą na pierwszym. Jeżeli układ liczb jest właśnie taki to wykonujemy żadnych czynności, w przeciwnym wypadku zamieniamy miejscami obie liczby korzystając ze zmiennej pomocniczej:

If Tab[1]>Tab[2] Then
  Begin
    Pom:=Tab[1];
    Tab[1]:=Tab[2];
    Tab[2]:=Pom;
  End;

Pierwszą liczbę przechowujemy w zmiennej pomocniczej, następnie kopiujemy liczbę drugą na miejsce pierwsze tablicy po czym przechowaną liczbę wpisujemy na miejsce drugie.
Po wykonaniu powyższej instrukcji większa z dwóch pierwszych liczb tablicy znajduje się na jej drugim miejscu. Możemy teraz wykonać taką samą instrukcję w stosunku do liczb drugiej i trzeciej:

If Tab[2]>Tab[3] Then
  Begin
    Pom:=Tab[2];
    Tab[2]:=Tab[3];
    Tab[3]:=Pom;
  End;

Ponieważ większa z dwóch pierwszych liczb była na miejscu drugim, to po wykonaniu tej instrukcji największa z trzech pierwszych liczb trafi na miejsce trzecie tablicy. Instrukcję powyższą wykonujemy N-1 razy - po ostatnim wykonaniu:

If Tab[N-1]>Tab[N] Then
  Begin
    Pom:=Tab[N-1];
    Tab[N-1]:=Tab[N];
    Tab[N]:=Pom;
  End;

największa liczba tablicy znajduje się na jej ostatnim N-tym miejscu.
Powyższy ciąg N-1 instrukcji warunkowych można zapisać przy pomocy następującej pętli For:

For I:=1 To N-1 Do
  If Tab[I]>Tab[I+1] Then
    Begin
      Pom:=Tab[I];
      Tab[I]:=Tab[I+1];
      Tab[I+1]:=Pom;
    End;

Skoro powyższa pętla powoduje przeniesienie największej spośród N pierwszych liczb w tablicy na miejsce N, to po zmniejszeniu liczby N o 1 i ponownym wynonaniu pętli największa spośród pozostałych N-1 pierwszych liczb zostanie przeniesiona na miejsce N-1. Po kolejmym zmniejszeniu N o jeden i wykonaniu pętli największa spośród pozostałych N-2 pierwszych liczb w tablicy zostanie przeniesiona na miejsce N-2. Proces ten powtarzamy do momentu N=2:

While N>1 Do
  Begin
    For I:=1 To N-1 Do
      If Tab[I]>Tab[I+1] Then
        Begin
          Pom:=Tab[I];
          Tab[I]:=Tab[I+1];
          Tab[I+1]:=Pom;
        End;
    Dec(N);
  End;

Powyższa pętla While wykonywana jest dokładnie N-1 razy. Można zamiast tej pętli używać pętli For korzystając z dodatkowego indeksu J:

For J:=1 To N-1 Do
  For I:=1 To N-1 Do
    If Tab[I]>Tab[I+1] Then
      Begin
        Pom:=Tab[I];
        Tab[I]:=Tab[I+1];
        Tab[I+1]:=Pom;
      End;

uzyskując w ten sposób nawet prostszy zapis.