My first Magazine pemrograman-kompetitif-dasar | Page 43

3.2 Pengurutan
1.
2.
3.
4.
Siapkan array kosong. Secara definisi, array yang kosong merupakan array terurut.
Secara bertahap, sisipkan elemen baru ke dalam array yang sudah terurut tersebut.
Penyisipan ini harus dilakukan sedemikian sehingga array tetap terurut.
Misalnya saat ini data yang sudah terurut adalah [1, 2, 3, 8], lalu elemen yang akan
disisipkan adalah 5, maka dihasilkan [1, 2, 3, 5, 8].
Prosesnya dapat digambarkan seperti pada Tabel 3.2
Tabel 3.2: Proses Pemindahan Data menjadi Terurut.
Data Asal
Data Terurut
[4, 3, 2, 8, 5, 3] []
[3, 2, 8, 5, 3]
[4]
[2, 8, 5, 3]
[3, 4]
[8, 5, 3]
[2, 3, 4]
[5, 3]
[2, 3, 4, 8]
[3]
[2, 3, 4, 5, 8]
[]
[2, 3, 3, 4, 5, 8]
Strategi yang dapat digunakan untuk menyisipkan angka adalah meletakkan angka yang
hendak disisipkan pada bagian paling belakang, lalu digiring mundur sampai posisinya tepat.
Misalnya pada kasus menyisipkan angka 3 pada data [1, 2, 5, 8, 9] seperti pada Gambar 3.11
3
1 2 5 8 9
1 2 5 8 9 3
1 2 5 8 3 9
1 2 5 3 8 9
1 2 3 5 8 9
selesai
Gambar 3.11: Ilustrasi penyisipan angka 3 pada data [1, 2, 5, 8, 9].
Implementasi Insertion Sort
Implementasi insertion sort dapat ditemukan pada Algoritma 14.
Algoritma 14 Algoritma insertion sort .
1:
2:
3:
4:
5:
6:
7:
8:
9:
procedure I NSERTION S ORT (h)
for i ← 1, N do
pos ← i
while ((pos > 1) ∧ (h[pos] < h[pos − 1])) do
SWAP (h[pos], h[pos − 1])
pos ← pos − 1
end while
end for
end procedure
. Selama belum tepat, giring ke depan
33