53
di
sebelah
kanan
elemen
ke-i.
Algoritma
Quicksort
mempunyai
kompleksitas
O(n log n).
2.8.5 Merge Sort
Mergesort
adalah pengurutan dengan cara penggabungan. Dua kumpulan
data yang masing-masing telah diurutkan digabung menjadi satu.
Penggabungan
dimulai
dengan
menggabungkan
kelompok
data
dengan
jumlah elemen terkecil, yaitu kelompok satu data digabung dengan kelompok
satu
data.
Algoritma
mergesort
mempunyai kompleksitas O(n log n) untuk
worst ase tetapi memerlukan memori yang lebih banyak.
2.8.6 Shell Sort
Cara
kerja
algoritma shellsort
mirip
dengan
algoritma
insertion sort.
Insertion sort
membandingkan elemen-elemen data yang berdekatan (berjarak
satu
posisi). Shell
sort
mengurutkan
elemen
berjarak
tertentu
(diminishing
distance)
misalnya
yang
berjarak
5
posisi,
lalu
berjarak 3
posisi
dan
yang
terakhir yang berjarak 1 posisi.
Diminishing distance
harus dicari sedemikian rupa sehingga tidak
mengulangi atau merusak hasil sorting sebelumnya.
 |