Сортирање спајањем

sortiranje_spajanjem.cpp


/*Ovaj program vrsi sortiranje niza prirodnih brojeva metodom sortiranja spajanjem. Osnovna
ideja ovog metoda je da podijelimo niz na pola i obe polovine sortiramo. Zatim te
dvije polovine spojimo ponovo na takav nacin da dobijemo sortirani niz.  Ovaj algoritam je rekurzivan i njegova slozenost je O(n*log(n)). Primjenjena je strategija "podijeli pa vladaj"; konstruisao ga je 1945. Dzon fon Nojman (John von Neumann)

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

#include
#include
using namespace std;

int a[11], b[11];

void Spoji(int k1, int k2)//vrsi spajanje sortiranih nizova
{
 int sredina, i, j, k;
 i=k1;//pocetni element prve polovine
 sredina=k1+(k2-k1)/2;
 j=sredina+1;//pocetni element druge polovine
 k=k1;
 while ((i<=sredina)&&(j<=k2))//zatim ih spojimo tj. slijemo jedan u drugi
 {
 if (a[i]<=a[j])
 {
 b[k]=a[i];
 i++;
 k++;
 }
 else
 {
 b[k]=a[j];
 j++;
 k++;
 }
 }
 if (i-1<sredina)
 for (j=i;j<=sredina;j++)
 {
 b[k]=a[j];
 k++;
 }
 if (j-1<k2)
 for (i=j;i<=k2;i++)
 {
 b[k]=a[i];
 k++;
 }
 for (i=k1;i<=k2;i++)
 a[i]=b[i];
}

void SortirajSpajanjem(int l1, int l2)//rekurzivna procedura (poziva samu sebe)
{
 if (l1<l2)
 {
SortirajSpajanjem(l1,l1+(l2-l1)/2);
SortirajSpajanjem(l1+(l2-l1)/2+1,l2);
 Spoji(l1,l2);
 }
}

int main()
{
 int n, l;
 cout<>a[n];
 if (a[n]==-1)
 {
 n=n-1;
 l=1;
 }
 }
 SortirajSpajanjem(1,n);//poziva proceduru za sortiranje unesenih elemenata
 cout< for (l=1;l<=n;l++)
 cout<<a[l]<<" ";
 getchar();
 return 0;
}

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

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

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

WordPress.com лого

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

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

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

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

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

Google+ photo

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

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