Sortiranje nizova

Sortiranje nizova u Pascal-u je operacija premeštanja elemenata niza tako da se posle njenog izvođenja dobije niz u kome su elementi uređeni po veličini. Premeštanje elemenata niza, tako da se dobije niz uređen po veličini je jedna od vrlo važnih i čestih operacija.

Niz može da se sortira na puno načina. Oni se dele na tzv. elementarne postupke sortiranja, u kojima se direktno koriste osnovne ideje za sortiranje, i složene postupke u kojima se eliminišu neki nedostaci elementarnih postupaka.

Skup je moguće urediti koristeći varijacije sledeća tri postupka:

  1. Sortiranje umetanjem (engl. insertion sort), je postupak za sortiranje u kome se prvi element iz nesortiranog dela niza ubacuje u sortirani deo na odovarajuće mesto.
  2. Sortiranje izabiranjem (engl. selection sort), je postupak za sortiranje u kome se u nesortiranom delu niza nalazi najmanji element i on postavi na početak nesortiranog dela.
  3. Sortiranje razmenom (engl. exchange sort), je postupak za sortiranje u kome dva susedna elementa razmene mesto ako „stoje pogrešno“.

Sve elementarne metode sortiranja funkcionišu tako, što se niz podeli na dva dela, sortirani deo i nesortirani deo, a u svakom algoritamskom koraku se sortirani deo povećava za jedan element. Uvek ćemo pretpostaviti da se sortirani deo nalazi na početku niza.

U nastavku je dat pregled nekih najčešćih metoda za sortiranje nizova. Za neke od nih je dat i odgovarajuči programski kod.

Sortiranje umetanjem Pri sortiranju umetanjem, sortirani deo se povećava tako što se prvi element nesortiranog dela „umetne“ na odgovarajuće mesto u sortirani deo.

PROGRAM sortiranje;

CONST maxniz = 10;

TYPE

    uporedivtip = INTEGER;

    element = RECORD

                kljuc : uporedivtip;

                ostalo : String

              END;

    niz = ARRAY [1..maxniz] OF element;

VAR i : INTEGER;

    B : niz;

 

PROCEDURE InsertionSort (VAR  a :  niz) ;

VAR

  i, j : INTEGER ;

  temp : element ;

 BEGIN

  FOR i  := 2 TO maxniz DO

   BEGIN

    temp := a [ i ] ;

    j := i – 1 ;

    WHILE ( j > 0 ) AND (temp. kljuc < a [ j ] . kljuc) DO

     BEGIN

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

      DEC ( j )

     END;

      a [ j+1 ]  := temp

    END

END;

 

BEGIN

   writeln(‘Unesite elemente niza’);

   FOR i := 1 to maxniz DO read(B[i].kljuc);

   InsertionSort(B);

   FOR i := 1 to maxniz DO write(B[i].kljuc : 6)

END.

 Sortiranje izabiranjem Sortiranje izabiranjem se organizuje tako da se u sortiranom delu niza nalaze elementi koji su manji od svih elemenata u nesortiranom delu. Sortirani deo niza se povećava za jedan, tako što se u nesortiranom delu nađe najmanji element i prebaci na početak nesortiranog dela. Tada su svi elementi u sortiranom delu opet manji od svih elemenata u nesortiranom delu niza.

Na početku je nesortirani deo prazan i najpre se nađe najmanji element u celom nizu, pa se prebaci na početak niza, zatim se u delu niza od drugog elementa pa do kraja nađe najmanji i on prebaci na drugo mesto itd. U poslednjem koraku se od dva zadnja elementa manji stavi na pretposlednje mesto.

Sortiranje razmenom Zbog ovog „isplivavanja“ najmanjih elemenata ovaj način sortiranja se naziva još i „sortiranje mehurićem“ (eng. bubble sort).

 PROGRAM sortiranje3;

CONST maxniz = 10;

TYPE

    uporedivtip = INTEGER;

    element = RECORD

                kljuc : uporedivtip;

                ostalo : String

              END;

    niz = ARRAY [1..maxniz] OF element;

VAR i : INTEGER;

    B : niz;

 

PROCEDURE BubbleSort (VAR a  :  niz) ;

VAR

  i, j: INTEGER;

  temp : element ;

 

BEGIN

  FOR i  := 1 TO maxniz -1 DO

   BEGIN

    FOR  j  := maxniz DOWNTO  i + 1  DO

      IF a [ j ] . kljuc  <  a [j – 1]. kljuc THEN

       BEGIN

        temp := a [ j – 1 ] ;

        a [ j – 1 ] :=  a [ j ] ;

        a [ j ]  := temp

       END

  END

END;

 BEGIN

   writeln(‘Unesite elemente niza’);

   FOR i := 1 to maxniz DO read(B[i].kljuc);

   BubbleSort(B);

   FOR i := 1 to maxniz DO write(B[i].kljuc : 6)

END.

S obzirom da postoji više elementarnih metoda sortiranja nizova za rešenje jednog problema, treba utvrditi koja od njih je bolja za konkretan problem, tj. koji postupak brže sortira elemente u datom slučaju. Pri tom treba brojati ukupan broj koraka, koji očigledno zavisi od veličine niza, a u detaljnijoj analizi ukupan broj upoređivanja i ukupan broj premeštanja.

S druge strane, brzina sortiranja će zavisiti i od početnog rasporeda elemenata u nizu koji se sortira. Najčešće se analiziraju tri slučaja koja zavise od rasporeda elemenata. Posmatra se broj operacija pri najpovoljnijem rasporedu elemenata za algoritam, pri najnepovoljnijem rasporedu i neki srednji broj operacija.

Iz analize elementarnih metoda sortiranja sledi da je sortiranje razmenom (BubbleSort) najgore, a da je sortiranje izabiranjem (SelectionSort) najbolje, ako su elementi niza veliki, pošto ima malo premeštanja kada se koristi ovaj metod sortiranja nizova. U slučaju da su elementi niza mali tada sortiranje umetanjem (InsertionSort) daje najbolje rezultate.

Zbog postojanja velikog broja različitih metoda sortiranja nizova, potrebno je prilikom rešavanja nekog konkretnog problema uzeti u obzir sve navedene osobine i odabrati najefikasniju metodu.

Ovaj unos je objavljen pod Programski jezik Pascal i označen sa , , . Zabeležite stalnu vezu.

Ostavite odgovor

Popunite detalje ispod ili pritisnite na ikonicu da biste se prijavili:

WordPress.com logo

Komentarišet koristeći svoj WordPress.com nalog. Odjavite se / Promeni )

Slika na Tviteru

Komentarišet koristeći svoj Twitter nalog. Odjavite se / Promeni )

Fejsbukova fotografija

Komentarišet koristeći svoj Facebook nalog. Odjavite se / Promeni )

Google+ photo

Komentarišet koristeći svoj Google+ nalog. Odjavite se / Promeni )

Povezivanje sa %s