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 perbandingan dan pertukaran.
Perbandingan dimulai dari separuh array yang akan disortir dengan separuh bagian yang lain.
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. Demikian seterusnya sampai 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
Contoh :
Jika terdapat 100 elemen, diperbandingkan elemen 1 dan elemen 51, elemen 2 dan elemen 52 dst. Selanjutnya algoritma akan membandingkan elemen 1 dan elemen 26, elemen 2 dan elemen 27 dst.
0 komentar:
Posting Komentar