Algorytmy » Sortowanie

Sortowanie Bąbelkowe 2

Sortowanie czasem się przydaje. Często w szkołach jako zadanie jest opracowanie sortowania bąbelkowego. Co to właściwie jest? Już wyjaśniam. Jest to najprostszy i zarazem najczęściej spotykany algorytm sortowania tablic. Polega na dwukrotnym wykonaniu na tablicy pętli for. W pętli następuje porównanie dwóch sąsiadujących ze sobą elementów. Jeżeli element wcześniejszy jest większy to następuje przesunięcie jego o jeden element do przodu. I tak jest to wykonywane tyle razy ile elementów ma dana tablica. Poniżej prezentuje kod służący do sortowania w Delphi:

type
  TList = array of Integer;
 
var List : TList;
 
procedure Sort(var Tab : TList);
var
  i, j : Integer;
  Temp : Integer;
begin
  for I := Low(Tab) to High(Tab) do
  begin
    for J := Low(Tab) to High(Tab) do
    begin
      if (Tab[j] > Tab[j-1]) then
      begin
        Temp := Tab[j];
        Tab[j] := Tab[j-1];
        Tab[j-1] := Temp;
      end;
    end;
  end;
end;


W tym programie zadeklarowałem nowy typ danych opartych na tablicach - TList. Jeżeli program napotka na większy element niż poprzednio edytowany to następuje zamiana elementów w tablicy.

A oto wykorzystanie powyższej procedury:

procedure TForm1.Button1Click(Sender: TObject);
var
  i : Integer;
begin
  SetLength(List, 3);
  List[0] := 4;
  List[1] := 34;
  List[2] := 1;
 
  Sort(List);
 
  for I := Low(List) to High(List) do
    Edit1.Text := Edit1.Text + ' ' + IntToStr(List[i]);
end;


Tutaj po naciśnięciu klawisza następuje dynamiczne dodania do tablicy elementów, a następnie w komponencie Edit przedstawienie po kolei wszystkich elementów.

To wszystko. Tak napisany program posortuje tablice od elementu największego do najmniejszego.

Przedstawię jeszcze jak powinien wyglądać taki algorytm w Perlu:

  for ($i=1; $i<=$#STAT; $i++) {
    for ($j=1; $j<=$#STAT; $j++) {
      if (@STAT[$j] > @STAT[$j-1]) {
        $temp = @STAT[$j];
        @STAT[$j] = @STAT[$j-1];
        @STAT[$j-1] = $temp;
      }
    }
  }


@STAT to oczywiście tablica...

2 komentarze

rikardo7 2006-01-07 17:50

Ten algorytm nie działa poprawnie !Sypie sie:)

piratt 2005-02-23 13:08

To nie jest optymalny kod sortowania babelkowego. O ile przy malych tablicach nie ma to duzego znaczenia to jesdnak przy wiekszych.. A oto kod ktory polecam:

int i,j, temp, done;
i=0;
do
{
    done = 1;
    for(j=0; j<rozmiar-i-1; j++)
    {
        if (tablica[j] > tablica[j+1])
        {
            temp=tablica[j];
            tablica[j]=tablica[j+1];
            tablica[j+1]=temp;
            done = 0;
        }
    }
    i++;
} while (!done);