Gradivo III razreda u Gimnaziji "Veljko Petrović"

Računarstvo i Informatika

Sortiranje

Postoje razni algoritmi za sortiranje raznih struktura podataka. Koji algoritam ćete koristiti zavisi od broja članova niza, vremenskog ili memorijskog ograničenja i sl.

Metoda zamene

Ova metoda je jednostavna za implementaciju, ali je spora. Vremensta složenost metode je O(n²) a prostorna O(n). Koristi se kada broj članova niza nije velik. Postupak je sledeći. U prvom prolazu kroz niz postavljamo najveći član niza na kraj (ili početak). To radimo tako što poredimo susedne članove u nizu i ako je prvi od posmatrana dva člana veći, zamenimo im mesta. U sledećem prolazu postavljamo sledeći član na svoje mesto a da pri tome imamo jedno poređenje manje, i sve tako dok nam ne preostanu poslednja dva člana u nizu.

Var N, i, j, pom : LongInt;

...

  For i := N-1 downto 1 do

    For j := 1 to i do

      if X[j] > X[j+1]

        then Begin

               Pom    := X[j];

               X[j]   := X[j+1];

               X[j+1] := Pom;

             end;

...

Boublle Sort

Ova metoda je je poboljšana metoda zamene. Prilikom svakog prolaza kroz niz broji se koliko puta je izvedena zamena članova. Ako u nekom prolazu nije bilo zamene, tada nema potrebe dalje da radimo jer to znači da je niz sortiran

Var i, j, pom, N  : LongInt;

       BiloZamene : Boolean;

...

  For i := N-1 downto 1 do

    Begin

      BiloZamene := False;

      For j := 1 to i do

        if X[j] > X[j+1]

          then Begin

                 Pom    := X[j];

                 X[j]   := X[j+1];

                 X[j+1] := Pom;

                 BiloZanmene := True;

               end;

      if not BiloZamene then exit;

    End;

...

Quick Sort

Empirijske studije pokazuju da je u opstem slucaju Quick Sort značajno brzi od ostalih brzih algoritama za sortiranje. Očekivana vremenska složenost algoritma je O(n log₂n) ali u najgorem slučaju, ona je O(n²). Ako Vam to nije dovoljno brzo, odlučite se na neku drugu metodu.

Donji algoritam je napisan kada se za PIVOT-a uzima srednji član niza (po položaju, ne po veličini).

Postupak: Pivota je potrebno postaviti na njegovo mesto u sortiranom nizu. Krećemo od leve granice i tražimo prvi veći član od pivota a zatim od desne granice i trazimo prvi manji član od pivota. Tim članovima niza zamenimo mesta. Prelazimo na sledeći sa obe strane i ponavljamo postupak dok se markeri ne sretnu. (ovaj postupak je opisan u Repeat Until petlji). Sada isti postupak primenimo i na levi i na desni podniz. To se radi rekurzivnim pozivom QuickSort Procedure. Ovaj algoritam je "u mestu" tj sortiranje se vrši u globalnom nizu X, u ovom slučaju članovi niza su tipa longint.

Procedure QuickSort(Levi, Desni:LongInt);

var i, j, D : LongInt;

var   Pom   : LongInt; { Pom je istog tipa kao i članovi niza }

Begin

  i := Levi;

  j := Desni;

  D := X[(Levi + Desni) div 2]; { PIVOT }

  Repeat

    while X[i] < d do i := i+1;

    while X[j] > d do j := j-1;

    if i <= j

      then Begin

             Pom    := X[i];

             X[i] := X[j];

             X[j] := Pom;

             j := j - 1;

             i := i + 1;

           end;

  until i > j;

  if Levi < j     then QuickSort(Levi, j);

  if    i < Desni then QuickSort(i, Desni);

end;