Сортирање бинарним уметањем

sortiranje_binarnim_umetanjem.cpp


/*Ovaj program vrsi sortiranje niza prirodnih brojeva metodom binarnog
umetanja. Razlikuje se od metode umetanja po algoritmu koji je u njemu primjenjen
za odredjivanje mjesta na koje treba umetnuti odgovarajuci element u sortirani
dio niza. Slozenost ovog algoritma je O(log(n)).

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

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
 int a[11];
 int i,n,x,L,D,m,j;
 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;}
 }
 for (i=2;i<=n;i++)
 {x=a[i];
 L=1;//lijevi kraj sortiranog dijela niza
 D=i-1;//desni kraj sortiranog dijela niza
 while (L<=D)//izlazak iz petlje kada se lijevi i desni kraj
 //sortiranog niza poklope
 {m=(L+D)/2;
 if (x<a[m])
 D=m-1;
 else L=m+1;
 }//ako je x u lijevoj polovini sortiranog niza pomjera
 //se desni kraj, u suprotnom pomjera se lijevi kraj
 for (j=i-1;j>=L;j--)
 a[j+1]=a[j];//pomjeranje sortiranog dijela niza udesno
 a[L]=x;//umetnuli smo x na odgovarajuce mjesto u sortiranom dijelu niza
 }
 cout<<"Sortiran niz (u rastucem redoslijedu):\n";
 for (i=1;i<=n;i++)
 cout<<a[i]<<" ";
 getchar();
 return 0;
}

Advertisements

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

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

WordPress.com лого

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

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

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

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

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

Google+ photo

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

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