Вишеструко сортирање уметањем

visestruko_sortiranje_umetanjem.cpp


/*Ovaj program vrsi sortiranje niza prirodnih brojeva metodom visestrukog sortiranja umetanjem (uveo ju je Donald L. Shell, po njemu je i dobila ime; Shellsort). Visestruko sortiranje umetanjem je
jednostavno prosirenje sortiranja umetanjem koje dopusta direktnu razmjenu
udaljenih elemenata. Prosirenje se sastoji u tome da se kroz algoritam umetanja
prolazi vise puta; u svakom prolazu uzima se neki korak h, dobija se niz u kome su
elementi na rastojanju h sortirani. Sa prolazima se nastavlja sve do koraka h=1,
u kome se dobija potpuno sortirani niz. Metodu visestrukog sortiranja umetanjem je tesko porediti sa drugim
zato sto je funkcionalni oblik vremena izvrsavanja nepoznat i zavisi od sekvence h.
Brzi je od svih algoritama u klasi slozenosti O(n^2). Metod nije
posebno osjetljiv na pocetni redoslijed elemenata, daje zadovoljavajuce vrijeme
izvrsavanja do npr. 5000 elemenata.

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],p[11];
 int i,n,h,j,x,k,l,m;
 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;
 }
 }
 i=0;
 while (3*i+1<=n)
 {
 h=3*i+1;
 i++;
 }//za h se uzima najvece 3*k+1 koje nije vece od n (Knut)
 //zgodno mada ne i optimalno u odnosu na vrijeme izvrsavanja algoritma
 i=-h-1;
 while (h>0)//postupak se ponavlja do h=1
 {
 i++;
 m=i;//na pocetku, m=-h; na kraju, m=-1
 j=0;
 while (m+h<=n)
 {
 m=m+h;//na pocetku, podniz koji krece od nultog elementa; na kraju, podniz koji krece od (h-1)-og elementa; m=0,1,...,h-1
 j++;
 p[j]=a[m];
 }//formiramo pomocni niz od svakog h-tog clana
 for (m=2;m<=j;m++)//pomocni niz ima j clanova
 {x=p[m];
 if (x<p[m-1])
 {
 k=1;
 while ((x>p[k])&&(k>=1)&&(k<m-1))
 k++;
 for (l=m-1;l>=k;l--)
 p[l+1]=p[l];
 p[k]=x;
 }
 }//sortirali smo pomocni niz metodom umetanja
 m=i;
 j=0;
 while (m+h<=n)
 {
 m=m+h;
 j++;
 a[m]=p[j];
 }//niz a je sortiran sa korakom h
 if (h==1)
 h=0;//nema izlaska iz petlje, sve dok se ne dobije korak h=1
 if ((h==2)&&(i==h-1))//ako su sortirani svi podnizovi elemenata sa rastojanjem h
 {
 h=1;
 i=-h-1;
 }
 if ((h>2)&&(i==h-1))//ako su sortirani svi podnizovi elemenata sa rastojanjem h
 {
 h=h/3;//sledeci korak je cjelobrojna trecina prethodnog
 i=-h-1;
 }
 }
 cout<<"Sortiran niz (u rastucem redoslijedu):\n";
 for (i=1;i<=n;i++)
 cout<<a[i]<<" ";
 getchar();
 return 0;
}

На сљедећем видео снимку имамо примјер вишеструког сортирања уметањем са корацима h=3, h=1.

Advertisements

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

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

WordPress.com лого

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

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

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

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

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

Google+ photo

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

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