Shell Sort Menggunakan Bahasa Pemograman C_Muh Akbar Tamrin_114012

18:47 Pemrograman Web 0 Comments

SHELL SORT (METODE SHORT)

Source Code

/*Shell sort*/
#include <iostream.h>
#include <conio.h>
int main (void)
{
 int array[5];
 int length=5;
 int i,d;
 int tmp, flag;
for (i=0;i<length;i++)
 {
 cout<<"Enter a number :";
 cin>>array[i];
 }
d=length;
 flag=i;

 while(flag||(d>1))
 {
 flag=0;
 d=(d+1)/2;
 for(i=0;i<(length-d);i++)
 {
 if(array [i+d]>array[i])
 {
 tmp=array[i+d];
 array[i+d]=array[i];
 array[i]=tmp;
 flag=1;
 }
 }
 }
for(i=0;i<5;i++)
 {
 cout<<array[i]<<endl;
 }
 getche();
}

Outputnya :


Shell Sort (Metode Shell) 
 
Metode ini disebut juga dengan metode pertambahan menurun (diminishing increment). Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959, sehingga sering disebut dengan Metode Shell Sort. Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan. Proses pengurutan dengan metode Shell dapat dijelaskan sebagai berikut :
 
Pertama-tama adalah menentukan jarak mula-mula dari data yang akan dibandingkan, yaitu N / 2. Data pertama dibandingkan dengan data dengan jarak N / 2. Apabila data pertama lebih besar dari data ke N / 2 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 2. Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-j selalu lebih kecil daripada data ke-(j + N / 2).

Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan data dengan jarak N / 4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4. Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4).

Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah 1.

Algoritma metode Shell dapat dituliskan sebagai berikut :

1. Jarak = N
2. Selama (Jarak > 1) kerjakan baris 3 sampai dengan 9
3. Jarak = Jarak / 2. Sudah = false
4. Kerjakan baris 4 sampai dengan 8 selama Sudah = false
5. Sudah = true
6. j = 0
7. Selama (j < N – Jarak) kerjakan baris 8 dan 9
8. Jika (Data[j] > Data[j + Jarak] maka tukar Data[j],
   Data[j + Jarak].
   Sudah = true
9. j = j + 1
Di bawah ini merupakan prosedur yang menggunakan metode Shell:

void ShellSort(int N)
{
int Jarak, i, j;
bool Sudah;
Jarak = N;
while(Lompat > 1)
{
Jarak = Jarak / 2;
Sudah = false;
while(!Sudah)
{
Sudah = true;
for(j=0; j<N-Jarak; j++)
{
i = j + Jarak;
if(Data[j] > Data[i])
{
Tukar(&Data[j], &Data[i]);
Sudah = false;
} } } } }
                                      
Shell sort disebut juga dengan metode pertambahan menurun (diminishing increment). Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959, sehingga sering disebut dengan Metode Shell Sort. Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan.


Shell Sort merupakan salah satu algoritma pengurutan yang lebih handal dibandingkan Selection Sort dan Bubble Sort. Kehandalannya yaitu: “Membagi deret data menjadi dua bagian. Masing-masing bagian diurutkan menggunakan Bubble Sort. Tidak menggunakan iterasi melainkan increment. Perulangan diakukan sesuai nilai increment.”

Proses pengurutan dengan Shell sort dapat disimulasikan sebagai berikut:

Pertama menentukan jarak mula-mula dari data yang akan dibandingkan, yaitu N/2. Data pertama dibandingkan dengan data dengan jarak N/2. Apabila data pertama lebih besar dari data ke N/2 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N/2. Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-j selalu lebih kecil daripada data ke-(j + N/2).

Pada proses berikutnya, digunakan jarak (N/2) / 2 atau N/4. Data pertama dibandingkan dengan data dengan jarak N/4. Apabila data pertama lebih besar dari data ke N/4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N/4. Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil dari data ke-(j + N/4).

Pada proses berikutnya, digunakan jarak (N/4) / 2 atau N/8. Demikian seterusnya sampai jarak yang digunakan adalah 1.

Penjelasan diatas adalah tentang metode pengurutan dengan menggunakan Shell Short. sekian yang bisa saya jelaskan. Mohon maaf atas kekurangannya Jika ada yang tidak dipahami atau ada diantara kalian yang ingin menambahkan  atau cuman sekedar kritik dan saran tinggal comment dibawah ini.

Link Github :

0 komentar: