SORTIRANJE NIZOVA

Sortiranje niza u neopadajućem ili nerastućem poretku podrazumeva nalaženje jedne permutacije elemenata niza u kojoj se elementi pojavljuju u neopadajućem tj. nerastućem poretku.

Sortiranje niza metodom izbora

Pretpostavimo da imamo zadat niz brojeva:

int A[]={2, 5, 11, 4, 1, 9, 0};

Da bi ga sortirali u npr. opadajućem poretku od najvećeg ka najmanjem, uradićemo sledeće:

Prolazimo redom kroz sve članove niza i pronalazimo najveći od svih i njega stavljamo na prvo mesto.
To radimo upoređivanjem tekućeg elementa A[ j ] sa elementom na prvom mestu A[ i ]. Ako naiđemo na veći vršimo zamenu ta dva elementa, tako da veći od njih ide na prvo mesto. U suprotnom uzimamo sledeći element za upoređivanje A[ j ] bez zamene. Nastavljamo dalje da ispitujemo i ako opet naiđemo na veći vršimo zamenu sve dok ne ispitamo sve elemente. Kad se ovo završi na prvom mestu je najveći od svih. U našem primeru, prvo bi 5 zamenili sa 2 i 5 bi se našlo na prvom i dalje kada naiđemo na 11 izvršili bi zamenu 5 i 11. Svi ostali brojevi su manji.

To radi sledeći kod:
int i=0;
for(int j = i+1; j<n; j++)
{
            if(A[j]>A[i]){
                  /*Zamena           */
                 int b=A[i];
                 A[i]=A[j];
                  A[j]=b;
               /* kraj zamene*/
            }
}
Sada kad smo našli najveći i stavili na prvo mesto ponavljamo postupak za preostale elemente i od njih tražimo najveći. Postupak je identičan samo ga primenjujemo na podniz koji nema već nađeni najveći element.

Postupak se ponavlja i za sledeći podniz gde se pronalazi največi za sve ostle članove sa desne strane izuzev prva dva. Ponavljanjem postupka imamo sve manje i manje podnizove koje sortiramo dok ne sortiramo do kraja.

Konačno ceo kod za sortiranje:

for(int i=0; i<N-1; i++)
{
for(int j=i+1; j<N; j++)
{
if(A[ j ] < A [ i ] )
{
int b=A[ i ];
A[ i ]=A[ j ];
A[ j ]=b;
}
}
}

Primer: Učitati broj elemenata niza n, a zatim zadati niz slučajno generisanih n celih brojeva čija je vrednost 0 - 100. Sortirati niz po opadajućem redosledu i ispisati na ekran.

Sortiranje metodom umetanja

#include <iostream>
#include<stdlib.h>

#define DIM 20
using namespace std;

int main()
{
int a[DIM], n, j;
cin>>n;
if(n<=0 || n>DIM) return 1;

//Ucitavanje elemenata niza
cout<<"Niz:"<<endl;
for (int i=0; i<n; i++){
//cin>>a[i];//4,2,8,9,1,5,6
a[i]=rand()%100;
cout<<a[ i ]<<" ";
}
cout<<endl;

//sortiranje niza
for(int i=0;i<n-1;i++){

for(j=i+1; j<n; j++){
if(a[ j ] > a[ i ]){
//Zamena
int b=a[i];
a[i]=a[j];
a[j]=b;

}

}

}
cout<<"sortirani niz:"<<endl;
for (int i=0; i<n; i++){
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}

Ako je dat niz (An) sa elementima nekog, uređenog tipa T, koji treba urediti u neopadajući poredak, ova metoda sortiranja polazi od pretpostavke da imamo uređen početni deo niza, (to svakako važi za i = 2, jer je podniz sa jednim elementom uređen) i u svakom koraku, počevši od i = 2 i povećanjem i, i-ti element se stavlja na pravo mesto u odnosu na prvih (uređenih) i - 1.
Prvo se trenutno ispitiani element aj skloni u pomoćnu promenljivu b. Posle toga se vrši uzastopno upoređivanje vrednosti aj i b za j=i-1,i-2,...,0. Svaki put kada se utvrdi da je aj>b, element aj se premešta na mesto aj+j. Ciklus upoređivanja i pomeranja završava se kada prvi put nije potrebno vršiti pomeranje ili kada j postane manje od nule.
Na kraju potrebno je još da se ispitana vrednost iz promenljive b stavi na svoje mesto, tj. u element aj+1.

Algoritam za sortiranje metodom umetanja

#include <iostream>
#define DIM 10
using namespace std;
/*Sortiranje niza metodom umetanja*/
int main()
{
int a[DIM], n, j;
cin>>n;
if(n<=0 || n>DIM) return 1;

//Ucitavanje elemenata niza
for (int i=0;i<n;i++){
cin>>a[i]; //4,2,8,9,1,5,6
}

//sortiranje niza
for(int i=1;i<n;i++){
int b=a[i];
for(j=i-1;j>=0;j--){
if(a[j]>b){
a[j+1]=a[j];
}
else break;
}
a[j+1]=b;
}
cout<<"sortirani niz:"<<endl;
for (int i=0;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}

Sortiranje niza objedinjavanjem (merge-sort engl)

Ideja je da se početni niz rekurzivno razdvaja na dva približno jednaka podniza, levi i desni. Zatim se postupak ponavlja sve dok se ne dođe do dva elementarna niza od 1 ili dva elementa.

Sortiranje objedinjavanjem

Brzo sortiranje(Quick-Sort engl.)

Algoritam sortiranja koji se pokazao najbržim. Sastoji se u rekurzivnom ponavljanju razdvajanja elemenata niza oko neke vrednosti koja je usvojena za "srednju". Pročitajte više o tome na stranici: Brzo Sortiranje

Prethodno
|< Osnovne strukture podataka