Pseudokod programa

Kako elemente u nizu preraspodeliti tako da oni budu uređeni u neopadajućem poretku tj. tako da važi

{X[0] ≤ X[1] ≤ ... ≤ X[n-1]}?

Postoji više načina da se to ostvari. Jedna od najjednostavnijih ideja je da se prodje kroz ceo niz i da se pri tom vrši zamena vrednosti prvog elementa u nizu i elementa na koji se naidje a koji je manji od prvog elementa u nizu. Na taj način, nakon prolaska kroz ceo niz, najmanji element niza biće postavljen na svoje mesto - na prvo mesto u nizu. Postupak dalje možemo da ponovimo počevši od drugog elementa u nizu, uporedjujući njegovu vrednost sa ostalim članovima niza i vršeći eventualne zamene. Postupak ponavljamo sve dok se podniz koji se obradjuje ne svede na jedan (poslednji) element niza.

Ovako opisan algoritam poznat je pod nazivom selection sort. Postoje i drugi algoritmi za sortiranje. Neki od njih su:

• algoritam zasnovan na razmeni susednih elemenata - bubble sort,
• algoritam metodom umetanja - insertion sort,
• algoritam metodom spajanja - merge sort,
• brzo sortiranje - quick sort.

Algoritam selection sort može se opisati sledećim koracima:

{X je niz dimenzije n, n ≥ 0}
Korak 1: Promenljivu i (indeks niza) postaviti na 0.
         Preći na korak 2.
Korak 2: Ukoliko je i ≤ n - 2(pretposlednji element niza)
         preći na korak 3,
         inače preći na korak 7.         
Korak 3: Promenljivu j postaviti na i + 1. 
         Preći na korak 4.
Korak 4: Ukoliko je j ≤ n-1(poslednji element niza)  
         preći na korak 5,
         inače, preći na korak 6.
Korak 5: Ukoliko je i-ti element niza veći od j-tog,
         razmeniti mesta i-tom i j-tom elementu.
         Vrednost promenljive j uvećati za jedan,
         odnosno preći na sledeći element u nizu.
         Preći na korak 4.
Korak 6: Vrednost promenljive i uvećati za jedan.
         Preći na korak 2.
Korak 7: Kraj
{X[0] ≤ X[1] ≤ ... ≤ X[n-1]}

{X je niz dimenzije n, n ≥ 0}
for i = 0 to n - 2 do
  begin 
    for j = i + 1 to n - 1 do
      begin 
        if (X[i] > X[j]) 
          begin 
            pom = X[i]; 
            X[i] = X[j]; 
            X[j] = pom ;
          end 
      end
  end
{X[0] ≤ X[1] ≤ ... ≤ X[n-1]}
  

Da li je ovaj program ispravan? Da li on zaista uređuje niz brojeva u neopadajućem poretku?

Naredna: Testiranje programa Gore: Selection sort Prethodna: Specifikacija   Sadržaj