Shell Sort

Shell Sort (Metode Shell) 

Metode ini disebut juga dengan metode pertambahan menurun (diminishing increment). 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 : 

1.    Menentukan  jarak mula-mula dari data yang akan dibandingkan, yaitu N

2.    Data pertama dibandingkan dengan data dengan jarak N / 2

3.    Apabila data pertama lebih besar dari data ke N / 2 tersebut maka kedua data tersebut ditukar.

4.    Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 2.

5.    Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-j selalu lebih kecil daripada data ke-(j + N / 2).

Langkah berikutnya :

1.    Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4

2.    Data pertama dibandingkan dengan data dengan jarak N / 4

3.     Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar

4.     Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4

5.     Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4)

6.    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

Kode Programnya :