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.
Source Image : https://www.computerhope.com/people/donald_shell.htm
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
Bagaimana Shell Sort Bekerja?
Mari kita perhatikan contoh berikut untuk memiliki gagasan tentang cara kerja Shell sort. Kami mengambil array yang sama yang telah kami gunakan dalam contoh kami sebelumnya. Untuk contoh dan kemudahan pemahaman kami, kami mengambil interval 4. Buat daftar sub-virtual dari semua nilai yang berada pada interval 4 posisi. Di sini nilai-nilai ini adalah {35, 14}, {33, 19}, {42, 27} dan {10, 44}
Disisni kita membandingkan nilai dalam setiap sub-daftar dan menukarkannya (jika perlu) dalam larik aslinya. Setelah langkah ini, array baru akan terlihat seperti ini
Kemudian, kita mengambil interval 2 dan celah ini menghasilkan dua sub-daftar - {14, 27, 35, 42}, {19, 10, 33, 44}
Kami membandingkan dan menukar nilai, jika diperlukan, dalam larik asli. Setelah langkah ini, array akan terlihat seperti ini -
Akhirnya, kita mengurutkan sisa array menggunakan interval nilai 1. Shell sort menggunakan semacam penyisipan untuk mengurutkan array.
Berikut adalah penggambaran langkah demi langkah -
Kelebihan dan kekurangan Shell sort :
Kelebihan Shell sort :
1. Algoritma ini sangat rapat dan mudah untuk diimplementasikan.
2. Operasi pertukarannya hanya dilakukan sekali saja.
3. Waktu pengurutan dapat lebih ditekan.
4. Mudah menggabungkannya kembali.
5. Kompleksitas selection sort relatif lebih kecil.
Kekurangan Shell Sort :
1. Membutuhkan method tambahan.
2. Sulit untuk membagi masalah.
Daftar Referensi :
1.https://betaraubd.wordpress.com/2012/11/23/kekurangan-dan-kelebihan-algoritma-insertion-sort-dan-sell-sort/
2.http://fjrarnote.blogspot.com/2015/01/pengertian-shell-sort-dan.html
