Selection Sort

Posted: November 13, 2010 in Algoritma & Struktur Data

Algoritma selanjutnya yang akan kita bahas adalah algoritma insertion sort. Pada algoritma ini, data yang

akan kita proses dibagi menjadi dua bagian, yaitu bagian kiri dan bagian kanan. Bagian kiri adalah bagian yang

akan diurutkan, sedangkan bagian kanan adalah bagian sisanya. Proses pengurutannya adalah dengan cara seakan-

akan nilai yang lebih kecil akan diselipkan (insert) diantara nilai-nilai yang tepan. Jumlah array di bagian kiri akan

perlahan-lahan bertambah banyak, hingga pada akhirnya semua data akan berada di array bagian kiri dengan

keadaan terurut. Untuk lebih jelasnya, mari kita lihat ilustrasi berikut:

Array yang akan kita proses adalah sebagai berikut:

3 10 4 6 2 5

o Kita akan bagi array ini menjadi dua blok, yaitu dengan blok kiri berisikan satu nilai.

3 10 4 6 2 5

o Karena hanya berisikan satu nilai, maka dianggap nilai berikut adalah sudah urut. Satu blok paling kiri dari blok kanan (yaitu blok yang berisikan nilai 10) akan kita masukkan ke blok kiri.

3 10 4 6 2 5

o Isi dari blok kiri akan kita proses, nilai-nilainya akan diurutkan. Nilai 10 akan dibandingkan dari nilai yang

paling kiri, yaitu 3. Karena 3<10, maka isi dari blok kiri tidak perlu diproses. Kita pindahkan satu blok lagi

ke blok kanan.

3 10 4 6 2 5

o Nilai yang baru masuk, yaitu 4 akan dibandingkan dengan 3 (karena 3<10, maka tidak perlu diproses), lalu dibandingkan dengan 10 (karena 10>4, maka isinya kita akan kita proses). Nilai 4 akan diselipkan (insert)

di antara nilai 3 dan 10, sehingga nilai 10 akan bergeser satu kotak. Urutannya menjadi:

3 4 10 6 2 5

o Pindahkan lagi satu blok ke blok kiri. Nilai 6 akan dibandingkan dengan 3 (no insertion needed), 4 (no

insertion needed), dan 10 (insertion needed). Nilai 6 akan kita sisipkan diantara nilai 4 dan 10. Nilai 10

akan digeser satu kotak. Urutannya menjadi:

3 4 6 10 2 5

o Pindahkan lagi satu blok ke blok kiri. Nilai 2 akan dibandingkan dengan 3 (insertion needed). Nilai 2 akan

kita sisipkan pada array yang paling depan. Otomatis semua array di sebelah kanannya akan bergeser.

Urutannya menjadi:

2 3 4 6 10

o Langkah terakhir, kita pindahkan blok terakhir dari blok kanan ke blok kiri. Kita bandingkan nilai 5 dengan

2 (no insertion needed), 3 (no insertion needed), 4 (no insertion needed), 6 (insertion needed). Nilai 5 akan

kita sisipkan di antara nilai 4 dan 6. Otomatis nilai 6 dan 10 akan bergeser satu kotak ke sebelah kanan.

Proses sorting selesai. Urutan akhirnya akan menjadi:

Source code:

2 3 4 5 6 10

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s