1. Insertion Sort (Bab 2)

By /

1. Insertion Sort

Insertion Sort adalah salah satu algoritma yang digunakan untuk permasalahan pengurutan dalam list (daftar objek). Sesuai namanya, insertion sort mengurutkan sebuah list dengan cara menyisipkan elemen satu per satu sesuai dengan urutan besar kecilnya elemen hingga semua elemen menjadi list yang terurut. Misalnya, dalam kasus mengurutkan elemen list dari yang terkecil hingga terbesar (ascending), tahap pertama ialah kita akan membaca suatu elemen dengan elemen yang berdekatan. Apabila elemen yang berdekatan dengan elemen saat ini lebih kecil, elemen yang lebih kecil akan ditukar dengan elemen yang lebih besar dan dibandingkan kembali dengan elemen-elemen sebelumnya yang sudah terurut. Apabila elemen saat ini sudah lebih besar dari elemen sebelumnya, iterasi berhenti. Hal ini dijalankan satu per satu hingga semua list menjadi terurut.

Langkah-Langkah Insertion Sort

Diberikan data:

2, 8, 1, 12, 3, 11

Data akan diurutkan dari nilai terkecil ke nilai terbesar (ascending) menggunakan metode Insertion Sort.

  1. Langkah 1

Elemen pertama, yaitu 2, dianggap sudah terurut.

[2] | 8  1  12  3  11

Bagian kiri merupakan data yang sudah terurut, sedangkan bagian kanan merupakan data yang belum terurut.

  1. Langkah 2

Ambil elemen 8 dan bandingkan dengan 2.

Karena 8 lebih besar dari 2, maka 8 tetap berada di sebelah kanan 2.

[2  8] | 1  12  3  11

Sekarang bagian [2 8] sudah terurut.

  1. Langkah 3

Ambil elemen 1.

Bandingkan 1 dengan 8. Karena 1 lebih kecil, maka 8 digeser ke kanan.

Kemudian bandingkan 1 dengan 2. Karena 1 juga lebih kecil dari 2, maka 2 digeser ke kanan.

Setelah itu, 1 disisipkan pada posisi yang tepat.

[1  2  8] | 12  3  11

  1. Langkah 4

Ambil elemen 12.

Bandingkan 12 dengan 8.

Karena 12 lebih besar dari 8, tidak ada elemen yang perlu digeser.

[1  2  8  12] | 3  11

Bagian kiri tetap dalam keadaan terurut.

  1. Langkah 5

Ambil elemen 3.

Bandingkan 3 dengan 12, 8, dan 2.

  • 3 lebih kecil dari 12 → 12 digeser ke kanan.
  • 3 lebih kecil dari 8 → 8 digeser ke kanan.
  • 3 lebih besar dari 2 → berhenti.

Kemudian 3 disisipkan setelah 2.

[1  2  3  8  12] | 11

  1. Langkah 6

Terakhir, ambil elemen 11.

Bandingkan 11 dengan 12.

Karena 11 lebih kecil dari 12, maka 12 digeser ke kanan.

Kemudian bandingkan 11 dengan 8.

Karena 11 lebih besar dari 8, maka 11 disisipkan setelah 8.

[1  2  3  8  11  12]

Hasil Akhir

Data awal:

2  8  1  12  3  11

Data Akhir

1  2  3  8  11  12

Untuk lebih memahami insertion sort, silakan tonton video dibawah:

 

Scroll to Top