Penemu : Donald Shell
Metode perbandingan dan pertukaran
Perbandingan dimulai dari separuh array yang akan disortir dengan separuh bagian yang lain.
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.
Algoritma Shell Sort
Penjelasan algoritma
Banyak = N
range = banyak / 2
while range <> 0
counter = 1
target = banyak-range
while counter<=target
kiri = counter
selesai = false
while selesai=false
kanan = kiri+range
if item (kiri)>= item
(kanan)
selesai = true
else
swap item (kiri) dan
item (kanan)
if kiri > range
kiri = kiri - range
else
selesai = true
end_if
end_if
end_while
counter = counter + 1
end_while
range = range / 2
end_while
Penjelasan algoritma
- Program akan dijalankan jika range<>0 terpenuhi
- Sebelum masuk putaran ditentukan range dan target
- Pada putaran ke-1, range = banyak/2
- Tiap putaran dimulai dari counter=1 sampai dengan counter=target
- Pada tiap counter dilakukan proses : kiri = counter dan selanjutnya,
- item(kiri) dibandingkan dengan item(kanan) dimana : kanan = kiri + range
- Jika item(kiri) >= item(kanan) maka proses selesai dan dilanjutkan counter atau mungkin putaran berikutnya
- Jika item(kiri) < item(kanan) maka terjadi pertukaran, selanjutnya :
- jika item kiri < range maka proses selesai dan dilanjutkan counter berikutnya
- jika kiri > range maka kiri = kiri - range dan proses dimulai dari awal pembandingan item(kiri) dan item(kanan) lagi
- Jika semua counter pada suatu putaran telah selesai maka range akan dihitung kembali yaitu : range = range/2.
- Jika range <> 0 maka program akan dijalankan sampai range = 0 berarti data telah terurut
 |
| Contoh Sederhana Shell Sort |
