Sortiranje

2. Sortiranje zamjenom elemenata (eng. Exchange sort)

Algoritam za sortiranje zamjenom jedan je od jednostavnijih algoritama i varijanta je Selection sorta. Učinkovit je za nizove s manjim brojem elemenata (do 500).

U prvom koraku, na prvo se mjesto dovodi najmanji broj, u drugom koraku, na drugo se mjesto dovodi najmanji od preostalih itd. Postupak se nastavlja sve dok se ne dobije potpuno sređeni niz.

Na koji način?

Postupak zamjene napravi se svaki put kad se pronađu dva elementa čiji je poredak obratan od redoslijeda sortiranja.

Vrijednost svakog elementa niza, počinjući od prvoga, uspoređuje se s vrijednosti elemenata koji dolaze iza njega. Ako je poredak dvaju elemenata koji se uspoređuju obratan od redoslijeda sortiranja, elementima se zamijene vrijednosti.

Podsjetimo se, varijablama x i y vrijednosti je moguće zamijeniti na više načina. Dva su najčešća:

• uporabom računskih radnji zbrajanja i oduzimanja

Ako su na početku dane varijable x=6 i y=4, niz naredbi

                                          x=x+y; → x = 6 + 4 = 10, y ostaje nepromijenjen

                                          y=x-y; → y = 10 – 4 = 6, x ostaje 10

                                          x=x-y;   → x = 10 – 6 = 4

daje vrijednosti x = 4 i y = 6.

• pomoćnom varijablom.

Ta se metoda može objasniti na sljedeći način: Na raspolaganju su dvije pune boce, jedna Coca-Cole, a druga Fante. Potrebno je Coca-Colu preliti u bocu Fante, a Fantu u bocu Coca-Cole. Jedini je način Coca-Colu preliti u pomoćnu posudu, zatim Fantu preliti u bocu Coca-Cole i na kraju Coca-Colu iz pomoćne posude preliti u bocu Fante! Taj se način primjenjuje i za zamjenu varijabli.

Promotrimo!

Ako su na početku dane varijable x=6 i y=4, niz naredbi

              t=x;   → vrijednost varijable x smješta se u pomoćnu varijablu t

              x=y;   → u varijablu x smješta se vrijednost varijable y, dakle x = 4

              y=t;   → u varijablu y smješta se vrijednost pomoćne varijable t, dakle y = 6

dat će vrijednosti x = 4 i y = 6.