My first Magazine pemrograman-kompetitif-dasar | Page 42

3 Pencarian dan Pengurutan
terkecil
4
2
3
terkecil
3
2 8 5 3
4 8 5 3
2 3 4 8 5
2 3 3 8 5
terkecil
belum terurut
terurut
3
4
...
Gambar 3.10: Ilustrasi jalannya selection sort .
Implementasi Selection Sort
Implementasi selection sort dapat ditemukan pada Algoritma 12.
Algoritma 13 Algoritma selection sort .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
procedure S ELECTION S ORT (h)
for i ← 1, N do
. Pencarian indeks terkecil
minIndex ← i
for j ← i + 1, N do
if (h[ j] < h[minIndex]) then
minIndex ← j
end if
end for
SWAP (h[i], h[minIndex])
end for
end procedure
Pencarian elemen terkecil dapat dilakukan dengan linear search . Berhubung perlu dilakukan
N kali linear search , maka kompleksitas selection sort adalah O(N 2 ).
Pengurutan Parsial
Cara kerja selection sort memungkinkan kita untuk melakukan partial sort. Jika kita hanya
tertarik dengan K elemen terkecil, kita bisa melakukan proses seleksi dan menukar pada selection
sort K kali. Dengan demikian, pencarian K elemen terkecil dapat dilakukan dalam O(KN), cukup
baik apabila K jauh lebih kecil dari N.
3.2.3 Insertion Sort
Berikut adalah langkah-langkah untuk melakukan insertion sort :
32