My first Magazine pemrograman-kompetitif-dasar | Page 41

3.2 Pengurutan
2
2
2
2
3
3
3
3
4
4
4
3
3
3
3
4
5
5
5
5
8
8
8
8
ditukar
tidak ditukar
Gambar 3.9: Ilustrasi penggiringan elemen ketiga terbesar ke posisi ketiga dari akhir.
Implementasi Bubble Sort
Implementasi Bubble Sort dapat ditemukan pada Algoritma 12.
Algoritma 12 Algoritma Bubble Sort .
1:
2:
3:
4:
5:
6:
7:
8:
9:
procedure B UBBLE S ORT (h)
for i ← 1, N − 1 do
for j ← 1, N − i do
if (h[ j] > h[ j + 1]) then
SWAP (h[ j], h[ j + 1])
end if
end for
end for
end procedure
. Tukar h[ j] dengan h[ j + 1]
Jika eksekusi ke-i mengakibatkan i elemen terbesar terletak di i posisi terakhir, maka
dibutuhkan N kali eksekusi hingga seluruh data terurut. Dalam sekali eksekusi, dilakukan iterasi
dari elemen pertama sampai elemen terakhir, yang kompleksitasnya berkisar antara O(1) sampai
O(N), tergantung eksekusi ke berapa. Secara rata-rata, kompleksitasnya setiap eksekusi adalah
O(N/2), yang bisa ditulis O(N). Total kompleksitas bubble sort adalah O(N 2 ).
3.2.2 Selection Sort
Berikut adalah langkah-langkah untuk melakukan selection sort :
1.
2.
3.
4.
Pilih elemen terkecil dari data, lalu pindahkan ke elemen pertama.
Pilih elemen terkecil dari data yang tersisa, lalu pindahkan ke elemen kedua.
Pilih elemen terkecil dari data yang tersisa, lalu pindahkan ke elemen ketiga.
... dan seterusnya sampai seluruh elemen terurut.
31