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 :
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.
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
METODE PENGURUTAN (SHELL SORT)
Metode ini disebut juga dengan metode
pertambahan menurun (diminishing increment short). Metode ini dikembangkan
oleh Donald L.shell pada tahun 1959,sehingga sering disebut dengan metode shell
short.
Metode ini mengurutkan data dengan cara membandingkan suatu
data lain yang memiliki jarak tentu sehingga membentuk sebuah sub-list-,
kemudian dilakukan penukaran apabila diperlukan.
Jarak yang dipakai didasarkan pada increment value atau
sequence number K.Misalnya sequence number yang dipakai adalah 5,3,1. tidak ada
pembuktianya disini bahwa bilangan tersebut adalah sequence number terbaik.
Setiap sup-list berisi setiap element ke-K dari kumpulan
element yang asli.
o Sebagai contoh :
Jika K=5 maka sub-list adalah sebagai berikut :
– s[0] s[5] s[10]…
– s[1] s[6] s[11]…
– s[2] s[7] s[12]…
– dst
o Begitu juga K=3 maka sub-listnya adalah :
– s[0] s[3] s[6]…
– s[1] s[4] s[7]…
– dst