cara kerja metode Shell sort pada c++

SOBAT WINDOWS

1 Mar, 2021

Metode Shell Sort

Metode ini dinamakan sesuai dengan penciptanya, yaitu D.L. Shell. Metode ini mirip dengan metode Bubble Sort, hanya saja perbandingan dilakukan bukan antara dua bilangan yang berurutan, akan tetapi antara dua bilangan dengan jarak tertentu. Jarak ditentukan dengan N Div 2, dimana N adalah banyaknya elemen array. Lakukan pertukaran tempat jika setiap kali perbandingan dipenuhi (lebih besar untuk urut menaik dan lebih kecil untuk urut menurun). Setiap kali perbandingan terhadap keseluruhan elemen selesai dilakukan, maka perbandingan yang baru dilakukan kembali dimana jarak diperoleh dengan Jarak Div 2 (jarak diperoleh dari Nilai jarak sebelumnya). Perbandingan keseluruhan dilakukan sampai Nilai jarak sama dengan 1 (satu). Pada saat jarak berNilai 1, maka metode Shell Sort sama dengan metode Bubble Sort.

Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan diurutkan secara menaik dengan metode Shell Sort: 25, 72, 30, 45, 20, 15, 6, 59. Urutan langkah pengurutannya seperti berikut.

Untuk pertama kalinya Nilai jarak (K) = 8 div 2 = 4 dan kita buat suatu counter C=0. Kemudian proses perbandingan dilakukan berturut-turut antara Nilai[0] dengan Nilai[4], jika Nilai[0]>Nilai[4] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[1] dengan Nilai[5], jika Nilai[1]>Nilai[5] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[2] dengan Nilai[6], jika Nilai[2]>Nilai[6] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[3] dengan Nilai[7], jika Nilai[3]>Nilai[7] maka lakukan pertukaran tempat kemudian Nilai C=1.

Karena Nilai K masih sama dengan 4 dan Nilai C=1, maka lakukan kembali proses perbandingan dengan menghitung Nilai jarak (K) sama dengan 4 div 2 =2 dan membuat Nilai C=0, sekarang proses perbandingan dilakukan berturut-turut antara Nilai[0] dengan Nilai[2], jika Nilai[0]>Nilai[2] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[1] dengan Nilai[3], jika Nilai[1]>Nilai[3] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[2] dengan Nilai[4], jika Nilai[2]>Nilai[4] maka lakukan pertukaran tempat dan jika tidak lanjutkan terhadap Nilai[3] dengan Nilai[5], jika Nilai[3]>Nilai[5] maka lakukan pertukaran dan jika tidak lanjutkan terhadap Nilai[4] dengan Nilai[6], jika Nilai[4]>Nilai[6] maka lakukan pertukaran dan jika tidak lanjutkan terhadap Nilai[5] dengan Nilai[7], jika Nilai[5]>Nilai[7] maka lakukan pertukaran tempat kemudian Nilai C=1.

Karena Nilai K masih sama dengan 2 dan Nilai C=1, maka lakukan kembali proses perbandingan dengan menghitung Nilai jarak(K) sama dengan 2 div 2 = 1 dan membuat Nilai C=0, sekarang proses perbandingan dilakukan berturut-turut antara Nilai[0] dengan Nilai[1], Nilai[1] dengan Nilai[2], Nilai[2] dengan Nilai[3], Nilai[3] dengan Nilai[4], Nilai[4] dengan Nilai[5], Nilai[5] dengan Nilai[6], dan Nilai[6]>Nilai[7], kemudian Nilai C=1 akan diperoleh hasil pertukaran setelah perbandingan seperti berikut.

6 15 20 25 45 30 50 72

Walaupun K telah berNilai sama dengan satu, tetapi Nilai C masih berNilai sama dengan 1 maka perbandingan harus diulang kembali dengan memberi Nilai C=0 dan Nilai K sama seperti sebelumnya yaitu sama dengan 1. Setelah dilakukan perbandingan maka hasilnya dapat diperoleh seperti berikut:

6 15 20 25 30 45 50 72

Karena Nilai C tidak lagi berubah menjadi 1 maka perbandingan telah berakhir dan hasil terakhir merupakan hasil pengurutan yang diharapkan.

/* Program Pengurutan Metode Shell Sort
  Pengurutan Secara Menaik
  Nama File : Lat_Sorting_06a */
  
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>
void main()
{
  int Nilai[20];
  int i, N, l, k;
  int temp, jarak, s;
  cout<<"Masukkan Banyak Bilangan : ";
  cin>>N;
  for(i=0; i<N; i++)
  {
    cout<<"Elemen ke-"<<i<<" : ";
    cin>>Nilai[i];
  }
  
  //Proses Cetak Sebelum diurutkan
  cout<<"\nData sebelum diurut : ";
  for(i=0; i<N; i++)
    cout<<setw(4)<<Nilai[i];
    
  //Proses Pengurutan
  jarak = N / 2;
  cout<<"\nJarak = "<<jarak;
  while(jarak >=1)
  {
    do
    {
      s=0;
      for(i=0; i<=(N-jarak)-1; i++)
      {
        k=i+jarak;
        if(Nilai[i] > Nilai[k])
        {
          temp = Nilai[i];
          Nilai[i] = Nilai[k];
          Nilai[k] = temp;
          s=1;
          for(l=0; l<N; l++)
            cout<<setw(4)<<Nilai[i];
          cout<<"\n\t";
          getch();
        }
      }
    }
    while(s!=0);
    jarak /= 2;
    cout<<"\nJarak= "<<jarak;
  }
  cout<<"\nData Setelah di urut : ";
  for(i=0; i<N; i++)
    cout<<setw(4)<<Nilai[i];
  getch();
}

Contoh: Misalkan kita mempunyai array Nilai sebanyak 8 elemen akan diurutkan secara menurun dengan metode Shell Sort: 25, 72, 30, 45, 20, 15, 6, 50. Urutan langkah pengurutannya seperti berikut.

Dengan cara yang sama untuk pengurutan secara menaik, dengan mengganti tanda > menjadi < maka akan diperoleh elemen array yang terurut secara menurun. Gunakan program Lat_Sorting_06b.

/* Program Pengurutan Metode Shell Sort
  Pengurutan Secara Menurun
  Nama File : Lat_Sorting_06b */
  
#include<iostream.h>
#include<conio.h>
#include<iomanip.h>
void main()
{
  int Nilai[20];
  int i, N, l, k;
  int temp, jarak, s;
  cout<<"Masukkan Banyak Bilangan : ";
  cin>>N;
  for(i=0; i<N; i++)
  {
    cout<<"Elemen ke-"<<i<<" : ";
    cin>>Nilai[i];
  }
  
  //Proses Cetak Sebelum diurutkan
  cout<<"\nData sebelum diurut : ";
  for(i=0; i<N; i++)
    cout<<setw(4)<<Nilai[i];
    
  //Proses Pengurutan
  jarak = N / 2;
  cout<<"\nJarak = "<<jarak;
  while(jarak >=1)
  {
    do
    {
      s=0;
      for(i=0; i<=(N-jarak)-1; i++)
      {
        k=i+jarak;
        if(Nilai[i] < Nilai[k])
        {
          temp = Nilai[i];
          Nilai[i] = Nilai[k];
          Nilai[k] = temp;
          s=1;
          for(l=0; l<N; l++)
            cout<<setw(4)<<Nilai[i];
          cout<<"\n\t";
          getch();
        }
      }
    }
    while(s!=0);
    jarak /= 2;
    cout<<"\nJarak= "<<jarak;
  }
  cout<<"\nData Setelah di urut : ";
  for(i=0; i<N; i++)
    cout<<setw(4)<<Nilai[i];
  getch();
}