Сортиране чрез вмъкване с намаляваща стъпка

(Сортиране по Shell)

 

Представлява подобрение на сортирането с пряко вмъкване. Предложено е от D.L.Shell през 1959г. Идеята е следната: Масивът се разделя на няколко подмасива, като всеки от тях се сортира по метода на прякото вмъкване. Подмасивите се формират от елементи, намиращи се на еднакво разстояние (еднаква стъпка) в масива. Масивите се обединяват, стъпката се намалява, и ново оформилите се подмасиви се сортират отново. Процедурата продължава докато стъпката стане 1. Тогава се сортира целият подмасив.

Предимството на метода е, че

1.      Избира се стъпка (например 4).

2.      Всички елементи, които се намират на разстояние тази стъпка един от друг се разглеждат като подмасив и се сортират по метода на прякото вмъкване.

Пример:

Елементите с индекси 0,4,8,12 и т.н. образуват първия подмасив;

елементите с индекси 1,5,9,13 и т.н. образуват втори подмасив;

елементите с индекси 2,6,10,14 и т.н. образуват трети подмасив;

елементите с индекси 3,7,11,15 и т.н. образуват четвърти подмасив.

3.      Стъпката се намалява и отново се изпълняват операциите, описани в т.2

4.      Процедурата продължава до достигане на стъпка равна на едно.

 

Пример:


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Възниква въпросът дали необходимостта от няколко преминавания, всяко едно от които включва всеки елемент, няма да доведе до повече работа?

Обаче всяка стъпка за сортиране включва или сравнително малък брой елементи, или елементите са достатъчно добре подредени и броят на необходимите размествания е сравнително малък.

Методът на Shell дава по-добри резултати при стъпки, които не са кратни на две. Кнут (Knuth) доказва, че един разумен избор на стъпки е редицата (написана в обратен ред).


1, 4, 13, 40, 121, ……,

където hк+1 = 3* hк+1

h0 = 1

или:

1, 3, 7, 15, 31, ………

където hк+1 = 2* hк+1

h0 = 1

 



 

 

 

 

 

 

                    

 

 

 

                                                    

                                   

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Сортиране по Shell

# include <iostream.h>

void input(float a[100], int &n)

{

  int i;

  cout<<"n=";

  for(i = 0; i<n;i++)

  {

      cout<<"a["<<i<<"]=";

      cin>>a[i];

  }

}

void output (float a[100], int n)

{

  int i;

  for(i=0;i<n;i++)

  {

       cout<<a[i]<<'\t';

  }

}

 

void Shell (float a[100], int n)

{

  int i, j, k, st;

  int h[4] = {9,5,3,1};

  float x;

  for(k=0;k<4;k++)

  {

        st=h[k];

        for(i=st;i<n;i++)

        {

                            x=a[i];

                            for(j=i-st;j>=0;j-=st)

                            {

                                     if(x>=a[j]) break;

                                     else a[j+st]=a[j];

                            }

                            a[j+st]=x;

                   }

  }

}

void main(void)

{

         int n;

         float a[100];

         input (a,n) ;

    Shell (a,n) ;

    output (a,n) ;

}