Сортирање дијељењем низова

sortiranje_dijeljenjem_nizova.cpp


/*Ovaj program vrsi sortiranje niza prirodnih brojeva metodom sortiranja dijeljenjem. Osnovna
ideja ove metode je da niz podijelimo proizvoljno odabranim elementom na dvije particije
tako da su u lijevoj elementi manji od njega, u desnoj veci od njega. Isto vazi i
za njihove indekse. Dobijene particije se particionisu dalje rekurzivno sve dok
ne dobijemo sortiran niz. Prosjecna slozenost ovog algoritma je O(n*log(n)) (u najgorem
slucaju iznosi O(n^2)).

Program je izvrsen na oba operativna sistema (Linux i Windows) u Code::Blocks IDE okruzenju.*/

#include <stdio.h>
#include <stdlib.h>//funkcija rand()
using namespace std;

int a[11];//globalna promjenjiva, vazi u cijelom programu dok lokalne promjenjive
//vaze samo u blokovima u kojima su deklarisane

int/*tip varijable koju vraca*/ Podijeli/*ime funkcije*/(int L,int D/*argumenti*/)
//;prototip funkcije, moze da se navede samostalno slijedi tijelo funkcije
//funkcija se sama po sebi zove definicija funkcije, sadrzi protoptip i tijelo
//u slucaju da se navede samo prototip na kraju programa se definise funkcija
{
 int r,t;
 r=abs(rand()%(D-L+1))+L;//generise slucajan broj iz segmenta [L,D]
 while (L<=D)//pretrazuje niz sa krajeva i razmjenjuje clanove koji nisu
 //na svojim mjestima (lijevo treba da budu elementi niza manji od a[r],
 //a desno veci
 {
 while (a[L]<=a[r]) L=L+1;
 while (a[D]>=a[r]) D=D-1;
 if (L<=D)
 {
 t=a[L];
 a[L]=a[D];
 a[D]=t;
 L=L+1;
 D=D-1;
 }
 }//kada se ta dva pretrazivanja sretnu a[r] se zamijeni sa jednim
 //od njih, zavisno od pozicije na kojoj se trenutno nalazi
 if (r>L)
 {
 t=a[r];
 a[r]=a[L];
 a[L]=t;
 r=L;
 }
 if (r<D)
 {
 t=a[r];
 a[r]=a[D];
 a[D]=t;
 r=D;
 }//vracamo r, poziciju na kojoj se odabrani element nalazi nakon
 //patricionisanja
 return r;
}

void/*procedura, ne vraca ni jedan tip*/ SortirajDijeljenjem(int LL,int DD)
{
 int p;
 if (DD>LL)
 {
 p=Podijeli(LL,DD);//vrsi se patricionisanje
 SortirajDijeljenjem(LL,p-1);//lijeva particija se patricionise
 SortirajDijeljenjem(p+1,DD);//desna patricija se patricionise
 //i tako dalje rekurzivno dok ne dobijemo sortiran niz
 }
}//funkcija je rekurzivna jer poziva sama sebe

int main()
{
 int i,n;
 cout<<"Unesite niz prirodnih brojeva; maksimalno 10 elem.(za kraj unosa unesite -1):\n";
 i=0;
 while (i!=-1)
 {i++;
 cin>>a[i];
 if (a[i]==-1)
 {
 n=i-1;
 i=-1;
 }
 }
 SortirajDijeljenjem(1,n);//sortiramo niz, pozivamo funkciju imenom i argumentima
 cout<<"Sortiran niz (u rastucem redoslijedu):\n";
 for (i=1;i<=n;i++)
 cout<<a[i]<<" ";
 getchar();
 return 0;
}

[vimeo http://vimeo.com/23952026]
Advertisements

Оставите одговор

Попуните детаље испод или притисните на иконицу да бисте се пријавили:

WordPress.com лого

Коментаришет користећи свој WordPress.com налог. Одјавите се / Промени )

Слика на Твитеру

Коментаришет користећи свој Twitter налог. Одјавите се / Промени )

Фејсбукова фотографија

Коментаришет користећи свој Facebook налог. Одјавите се / Промени )

Google+ photo

Коментаришет користећи свој Google+ налог. Одјавите се / Промени )

Повезивање са %s