Insertion Sort: Metode Pengurutan Data dengan Menempatkan Setiap Elemen Data pada Posisinya, Bagaimana Cara Kerjanya?

Insertion sort adalah salah satu algoritma pengurutan yang lebih simple dalam paradigma pengurutan. Prinsip kerja algoritma ini melibatkan pengecekan setiap elemen dalam data dan menempatkannya pada posisi yang tepat dalam urutan yang telah disortir.

Cara Kerja Insertion Sort

Berikut ini adalah langkah-langkah yang dijalankan dalam insertion sort:

1. Pilih Elemen Data: Pada awal insertion sort, elemen pertama dianggap sebagai bagian dari daftar terurut. Kemudian, elemen berikutnya (yaitu elemen kedua) dipilih untuk diurutkan dan dimasukkan ke dalam urutan yang tepat pada bagian daftar yang telah disortir.
2. Bandingkan dan Tempatkan: Elemen ini kemudian dibandingkan dengan elemen-elemen dalam urutan yang sudah disortir. Jika elemen yang dipilih lebih kecil dari salah satu elemen dalam urutan, maka elemen tersebut dipindahkan ke posisi sebelum elemen yang lebih besar. Proses ini diulangi sampai elemen yang dipilih berada pada posisi yang benar dalam urutan yang disortir.
3. Lanjutkan dengan Elemen Berikutnya: Setelah suatu elemen disejajarkan, elemen data berikutnya dipilih dan proses pengurutan berulang. Hal ini terus dilakukan sampai semua elemen dalam daftar telah ditempatkan pada posisi yang benar, sehingga sekarang seluruh daftar data telah disortir.

Teknik ini adalah metode pengurutan in-place, karena tidak memerlukan ruang tambahan yang signifikan selain dari memori yang diperlukan untuk menampung daftar masukan. Algoritma ini juga stabil yang berarti menempatkan elemen dengan nilai yang sama dalam urutan yang sama sebagaimana mereka muncul di daftar input.

Kelemahan utama dari insertion sort adalah efisiensi pada daftar yang lebih besar. Karena algoritma memerlukan lebih banyak komparasi dan pergeseran elemen, ini bukan pilihan yang baik untuk daftar dengan banyak elemen.

Bagaimanapun, insertion sort merupakan pilihan yang baik untuk daftar yang hampir tersortir atau daftar dengan jumlah elemen kecil, karena kapasitasnya untuk mengurutkan daftar tersebut dalam waktu yang relatif cepat dan membutuhkan sedikit sumber daya.