Bagi yang terbiasa dengan pemrograman komputer, pasti sering menemukan data berupa angka yang berantakan. Data angka yang berantakan tersebut dapat diurutkan dengan bahasa pemrograman. Pengurutan tersebut dengan menggunakan suatu algoritma yang disebut algoritma algoritma sorting.
Terdapat beberapa algoritma sorting yang bisa digunakan untuk pengurutan data. Salah satunya yaitu algoritma insertion sort. Algoritma insertion sort inilah yang akan dibahas dalam artikel ini.
Section Artikel
Apa itu Algoritma Insertion Sort?
Asal kata insertion adalah insert yang artinya memasukkan atau menyisipkan. Maka algoritma insertion sort adalah algoritma untuk pengurutan data dengan cara mengambil elemen pada array, selanjutnya data tersebut akan disisipkan pada posisi yang seharusnya. Elemen pertama dan elemen yang sudah diurutkan akan dibandingkan. Perbandingan tersebut akan terus dilakukan sampai elemen tidak ada yang tersisa, atau sampai semua elemen telah diurutkan.
Cara kerja algoritma ini yaitu dengan melakukan perulangan. Pada setiap perulangannya, insertion sort akan memindahkan nilai elemen untuk kemudian disisipkan. Hal tersebut akan dilakukan secara berulang, sehingga semua elemen telah berada di posisi yang tepat.
Perbedaan Algoritma Insertion Sort dan Selection Sort
Selain algoritma insertion sort, algoritma lain yang sering digunakan untuk mengurutkan data ada algoritma selection sort. Terdapat perbedaan antara kedua algoritma tersebut.
Berikut ini tabel perbedaan algoritma insertion sort dan algoritma selection sort:
| NO | Algoritma Insertion Sort | Algoritma Selection Sort |
| 1 | Pengurutan data dilakukan dengan menyisipkan elemen data dari data yang belum diurutkan, kemudian menempatkan elemen data tersebut pada posisi yang tepat. | Pengurutan data dengan cara memilih elemen data dari yang memiliki nilai paling rendah, lalu menukar elemen tersebut dengan elemen ke i. Nilai dari i dimulai dari 1 ke n, dengan nilai n adalah jumlah semua elemen dikurangi satu. |
| 2 | Membandingkan data kedua dengan data kesatu. | Pengecekan data dimulai dari data 1 sampai data ke n. |
| 3 | Posisi data akan ditukar apabila data kedua lebih kecil dibanding data kesatu. | Penentuan bilangan berdasarkan indeks terkecil dari data pada bilangan tersebut. |
| 4 | Data ketiga dibandingkan dengan data kesatu dan data kedua. | Menukar bilangan index terkecil dengan bilangan pertama. |
| 5 | Jika data ketiga lebih kecil, maka posisinya akan ditukar. | Akan seterusnya begitu hingga semua data selesai diurutkan. |
| 6 | Data keempat akan dibandingkan dengan data kesatu, data kedua, dan data ketiga. | |
| 7 | Akan dilakukan pertukaran posisi apabila data keempat lebih kecil. | |
| 8 | Proses seperti di atas akan terus dilanjutkan sampai semua data selesai dipindahkan atau diurutkan pada posisinya masing-masing dengan tepat. |
Cara Kerja Algoritma Insertion Sort
Sebagaimana telah sedikit dijelaskan di atas, bahwa algoritma insertion sort mengurutkan data dengan cara kerjanya yaitu membagi elemen data menjadi dua bagian. Kedua bagian tersebut yaitu bagian yang belum diurutkan dan bagian yang sudah diurutkan.
Pada proses pengurutan awal, bagian yang sudah diurutkan hanya akan terdiri dari satu elemen, yakni elemen pertama dari data tersebut. Selanjutnya algoritma akan memproses pengurutan lebih lanjut dan mengulangi langkah sebelumnya, untuk mengambil elemen data yang belum diurutkan. Lalu akan menyisipkan atau memasukkan elemen tersebut pada tempat yang tepat.
Supaya lebih jelasnya, perhatikan penjelasan langkah-langkah cara kerja algoritma insertion sort:
- Langkah pertama, mulai dengan elemen data yang akan diurutkan.
- Selanjutnya menentukan elemen pertama untuk bagian kedua atau bagian yang sudah diurutkan..
- Kemudian ambil elemen berikutnya dari bagian elemen data yang belum diurutkan, lalu simpan di dalam suatu variabel sementara (contohnya, disebut “key”).
- Langkah selanjutnya bandingkan elemen data pada variabel sementara dengan setiap elemen yang terdapat pada bagian elemen data yang sudah diurutkan, dimulai dari kanan ke kiri.
- Apabila elemen pada bagian elemen data yang sudah diurutkan lebih besar dari elemen variabel sementara, geser elemen tersebut ke posisi berikutnya supaya ada ruang untuk menyisipkan elemen sementara.
- Ulangi langkah 4 dan 5 hingga elemen sementara sudah ditempatkan pada posisi yang tepat dalam bagian elemen data yang sudah diurutkan.
- Masukkan elemen pada variabel sementara pada posisi yang tepat di dalam bagian elemen yang sudah diurutkan.
- Ulangi langkah 3 sampai langkah 7 hingga seluruh elemen data selesai diurutkan.
Contoh Implementasi Algoritma Insertion Sort
Di bawah ini merupakan contoh implementasi algoritma insertion sort. Ada dua contoh, yaitu implementasi pada Python dan Implementasi pada C++.
Contoh Implementasi Algoritma Insertion Sort pada Python
Contoh implementasi algoritma insertion sort pada Python seperti yang terdapat di bawah ini:
Output:
Data yang diurutkan adalah 11, 12, 22, 25, 34, 64, 90
Contoh Implementasi Algoritma Insertion Sort pada C++
Sedangkan di bawah ini merupakan contoh implementasi algoritma insertion sort pada C++:
Output:
Elemen data sebelum diurutkan: 64 34 25 12 22 11 90
Elemen data setelah diurutkan: 11 12 22 25 34 64 90
Demikianlah penjelasan tentang algoritma insertion sort. Algoritma ini banyak dipilih sebagai algoritma pengurutan data karena memiliki beberapa kelebihan. Kelebihannya antara lain sederhana dan mudah dipahami, sehingga mudah diterapkan hanya dengan sedikit baris kode. Selain itu juga stabil dalam mengurutkan datanya, serta efisien juga digunakan untuk data terurut meskipun jumlahnya sedikit.
