Sortiranje

2. Sortiranje zamjenom elemenata (eng. Exchange sort)

2.1. Algoritam

Promotrimo na primjeru.

Neka su u niz A upisane ove vrijednosti:

U prvom prolasku kroz niz obave se sljedeći koraci (Prvi element uspoređuje se sa svim ostalim elementima. Kada naiđe na manji, zamjene mjesta u nizu):

Rezultat je nakon prvog prolaska kroz niz sljedeći:

→ Najmanji element niza doveden je na prvo mjesto.

U drugom prolasku kroz polje ponavlja se isti postupak s time da se drugi element uspoređuje s ostalim elementima niza, a prvi element se ne dira.

Rezultat je niz

→ i drugi je element doveden na njegovo mjesto.

U trećem prolasku kroz niz uzima se treći element i njegova se vrijednost uspoređuje s vrijednostima 4. i 5. elementa.

Rezultat je sljedeći:

Na kraju, u četvrtom prolasku kroz niz uspoređuju se vrijednosti 4. i 5. elementa.

Rezultat je niz u kojem su vrijednosti elemenata poredane u rastućem redoslijedu.

Algoritam za sortiranje na opisani način možemo zapisati na sljedeći način:

za i=1 do n-1 činiti
za j=i+1 do n činiti
ako je a[i]> a[j] onda

zamijeni(a[i],a[j])

Zapisano u programskom jeziku C:

for (i=0;i<n-1;i++)
for (j=i+1;j<n;j++)
    if (a[i]>a[j])
    {
       t=a[i];
       a[i]=a[j];
       a[j]=t;
}