Akibat dari ketidakefektifan algoritma Bubble Sort, muncul berbagai cara agar algoritma Bubble Sort lebih efisien. Dari berbagai cara ini muncul variasi-variasi baru dari Bubble Sort, beberapa diantaranya adalah:
- Modifikasi algoritma bubble sort
- Cocktail sort
- Comp sort
Modifikasi algoritma bubble sort dilakukan sehingga pseudocode menjadi seperti berikut.
procedure bubbleSort( A : list of
sortable items ) defined as:
n := length( A )
do
swapped := false
for each i in 0 to n - 1 inclusive
do:
if A[ i ] > A[ i + 1 ] then
swap( A[ i ], A[ i + 1 ] )
swapped := true
end if
end for
n := n - 1
while swapped
end procedure
Proses algoritma yang terjadi akan menjadi
T(n)=n(n-1)/2 (5)
Pada proses di atas, kompleksitas algoritma tetap O(n2). Akan tetapi, pada worst case, waktu pemrosesan akan berjalan dua kali lebih cepat daripada algoritma bubble sort biasa.
Pada cocktail sort, pseudocode-nya adalah sebagai berikut.
procedure cocktailSort( A : list of
sortable items ) defined as:
do
swapped := false
for each i in 0 to length( A ) - 2
do:
if A[ i ] > A[ i + 1 ] then
swap( A[ i ], A[ i + 1 ] ) //
swapped := true
end if
end for
if swapped = false then
break do-while loop
end if
swapped := false
for each i in length( A ) - 2 to 0
do:
if A[ i ] > A[ i + 1 ] then
swap( A[ i ], A[ i + 1 ] )
swapped := true
end if
end for
while swapped
end procedure
Pada algoritma cocktail-sort, ide dasarnya adalah dalam satu pass, elemen terkecil dan terbesar akan berada pada tempat yang tepat. Setelah itu, algoritma diulang tanpa melibatkan elemen awal dan akhir. Hal ini menghilangkan “kura-kura” dan mengakibatkan jumlah operasi berkurang. Akan tetapi, pada worst case, algoritma ini masih memiliki kompleksitas algoritma O(n2).
Sedangkan pada comb sort, pseudocode-nya adalah sebagai berikut.
function combsort(array input)
gap := input.size
loop until gap <= 1 and swaps = 0
gap := int(gap / 1.25)
i := 0
swaps := 0
loop until i + gap >=
input.size
if input[i] > input[i+gap]
swap(input[i],
input[i+gap])
swaps := 1
end if
i := i + 1
end loop
end loop
end function
Ide dari combsort adalah perbandingan antara elemen tidak dengan elemen sebelahnya, namun dimulai dengan gap sebesar panjang list data yang akan diurut, dibagi dengan suatu faktor. Faktor itu disebut shrink factor.
Sebagai contoh, suatu list dengan jumlah elemen 7, maka dengan shrink factor sebesar 1.3, masing –masing gap adalah 5,3,2,1. Dengan kata lain, pada awalnya elemen ke-1 dibandingkan dengan elemen ke-6, kemudian dilihat apakah ditukar atau tidak. Setelah itu ulangi dengan melakukan sorting dengan gap 3, kemudian 2, 1, dan seterusnya. Hasil kompleksitas algoritma worst case dari comb sort adalah O(n log n).
::. Selamat Belajar, Semoga Bermanfaat .::
No comments:
Post a Comment