Sortiranje niza

Sortiranje nizova je uređivanje elemenata niza u nekom poretku.

Rastući poredak: svaki element niza je veći od prethodnog elementa.

Opadajući poredak: svaki element niza je manji od prethodnog.

Neopadajući poredak: svaki element niza nije manji od prethodnog elementa.

Nerastući poredak: svaki element niza nije veći od prethodnog elementa.

Postoji puno načina - algoritama koji vrše sortiranje nizova. Pored načina ređanja elemenata niza u neki od navedenih poretka vrlo bitna je i brzina izvršavanja tog algoritma.

Da ponovimo još jednom, ali na malo drugačiji način:

Za numerički niz se kaže da je sortiran ili uređen kao:

1) rastući, ako je  a[0]  <  a[1]  <  a[2]  <  ...  <  a[n-1]

2) neopadajući, ako je  a[0]  < =  a[1]  < =  a[2]  < =  ...  < =  a[n-1]

3) opadajući, ako je  a[0]  >  a[1]  >  a[2]  >  ... .  a[n-1]

4) nerastući, ako je  a[0] >= a[1] >= a[2] >= ... >= a[n-1]

Jedan od osnovnih načina za sortiranje niza a[] koji sadrži n elemenata u neopadajući poredak je dat u nastavku:

1
2
3
4
5
6
7
8
9

for(i=0;i<n-1;i++)
	for(j=i+1;j<n;j++)
		if(a[i]>a[j])
		{
			/*razmena mesta elementima a[i] i a[j] */
			pom=a[i];
			a[i]=a[j];
			a[j]=pom;
		}

Kada želimo nerastući poredak onda se samo zameni znak u if naredbi tj. pišemo a[i]<a[j].

Primer:

Napisati program koji metodom slučajnog izbora formira niz celih brojeva od 200 elemenata (elementi su brojevi od 0-999), pa ga zatim sortira u neopadajućem poredku i prikazuje sve elemente sortiranog niza.

Rešenje:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#define n 200
#include<stdlib.h>
#include<stdio.h>

 int main(void)
 {

                 int a[n];  
 int i,j,x,pom;    

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

 for(i=0;i<n;i++)  
 printf("%d, ",a[i]); 

 return 0; 
 }

VAŽNO!!! Da biste mogli da sortirate niz u redosledu koji vam je zadat, nije neophodno da znate sve vrste algoritama za sortiranje - dovoljno je da znate BAR JEDAN NAČIN na koji se može urediti niz (za potrebe rada na času i za proveru znanja koja sledi u skorije vreme).

Dalje - - - > Za one koji žele da znaju više:

Na dnu strane se nalazi LINK ka objašnjenjima kako se može realizovati svaki od navedenih načina sortiranja nizova, mada se u istom fejlu nalazi i objašnjenje kako se vrši pretraživanje nizova, kao i LINK ka primeru rešenog zadatka

U nastavku će biti data objašnjenja pojedinih načina za sortiranje nizova :

Neki od najkorišćenijih algoritama za sortiranje nizova:

• Bubble Sort
• Insertion Sort (sortiranje umetanjem)
• Selection Sort
• Quick Sort
• Merge Sort

1. Bubble sort:

Funkcionisanje Bubble sort algoritma za sortiranje nizova se zasniva na principu međusobne zamene elemenata.

1. Prolazimo kroz niz i poredimo dva susedna elementa - ako nisu u dobrom poretku menjamo im redosled
2. Ako je pri prolasku bilo promena ponavljamo korak 1.

/* Najjednostavnija implementacija - menjamo uzastopne dok god ima promena - u ovom primeru sortiramo niz u rastućem redosledu */

int bilo_zamena, i, tmp;

do {

bilo_zamena = 0;

for (i = 0; i < n-1; i++)

if (a[ i ] > a[ i+1 ])

{

tmp=a[i];     /*vrsimo zamenu sadrzaja elemenata niza */

a[i]=a[i+1];

a[i+1]=tmp;

bilo_zamena = 1;

}

} while(bilo_zamena);

Malo ubrzanje se može postići ukoliko se primeti da posle svakog prolaza najveći ispliva na kraj, tako da se svaki naredni prolaz skraćuje za jednu poziciju.

U nastavku je data ideja kako to uraditi (pseudokod) - a vi razmislite kako to može da se upotrebi u programu:

for (i = 1..n) {
    for (j = 1..n-i) {
      if (a[j]>a[j+1]) {
        zameni(j, j+1);
      }
    }
  }

Ideja ovog algoritma:

• Upoređujemo prvi i drugi elemenat - ako nisu poređani kako se traži, menjamo im mesta
• Onda upoređujemo drugi i treći element, opet, ako nisu poređani, menjamo im mesta
  ...
• tako nastavljamo da upoređujemo dva po dva elementa i da im menjamo mesta ako je potrebno sve dok ne doguramo do kraja
  (u tom trenutku je poslednji element garantovano najveći (ako uređujemo u redosledu da su na početku manji a na kraju veći brojevi - rastući ili neopadajući), dok su svi ostali elementi za po malo pomereni u pravom smeru)
• zatim sve to radimo ispočetka, ali ne idemo do poslednjeg već do pretposlednjeg elementa (ako hoćemo da radimo malo brže i da ne prolazimo u onom delu niza koji je postavljen u željenom redosledu)
  
  neko opšte pravilo bi bilo:
• upoređujemo dva-po-dva elementa i menjamo im mesta ako nisu raspoređeni kako se traži, sve dok ne stignemo do sortiranog dela niza, kada počinjemo postupak ispočetka

Naziv ovog algoritma upravo i potiče iz ponašanja elemenata, pošto elementi koje sortiramo, kao mehurići, malo po malo, idu ka svojim mestima.

Bubble sort se često uzima kao primer lošeg algoritma. Razmislite - da bismo sortirali N elemenata moramo imati N prolazaka, doduše kroz sve manji i manji deo niza. Suštinski prvo prolazimo kroz N-1, pa kroz N-2, onda kroz N-3 itd. elemenata, što ukupno izađe oko N²/2 upoređivanja, dok broj razmena zavisi od početnog stanja niza.

LINKOVI:

Metode sortiranja nizova (link)

- - - > Primer sortiranja metodom izbora (link) sa objašnjenjem