SORTIRANJE NIZOVA

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 ajskloni u pomoćnu promenljivu b. Posle toga se vrši uzastopno upoređivanje vrednosti aj ib 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)

---

Brzo sortiranje(Quick-Sort engl.)

---

---