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

sortiranje_umetanjem.cpp


/*Ovaj program vrsi sortiranje niza prirodnih brojeva metodom umetanja.
Osnovna ideja na kojoj se zasniva ova metoda je da polazeci od pocetnog dijela
niza koji je vec sortiran, u ovom slucaju od prvog elementa, prvi sljedeci
element umecemo na odgovarajuce mjesto u sortirani niz, tako da dobijamo novi
sortirani niz. Ponavljajuci ovaj postupak n-1 puta dobija se sortiran niz.
Slozenost ovog algoritma je O(n^2).

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,j,k;
 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];//prvi clan neuredjenog dijela niza
 if (x<a[i-1])
 {j=1;
 while ((x>a[j])&&(j>=1)&&(j<i-1))
 j++;//x<=a[j], prvo takvo j
 for (k=i-1;k>=j;k--)//dekrementacija
 a[k+1]=a[k];//pomjeramo sortirani dio niza udesno
 a[j]=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