Insertion Sort: Pengertian, Cara Kerja, dan Implementasinya

Siti Khadijah Azzukhruf Firdausi

•

28 February 2024

•

3797

Pengurutan data adalah salah satu kunci untuk mengolah data secara efisien. Insertion sort adalah salah satu metode yang bisa mewujudkan hal tersebut. Pasalnya, insertion sort adalah salah satu algoritma pengurutan paling fundamental.

Algoritma ini bisa mengurutkan elemen dalam array dan memasukkannya ke posisi yang tepat. Ingin tahu lengkapnya? Baca artikel ini sampai habis ya!

Apa yang Dimaksud dengan Insertion Sort?

Insertion sort adalah sebuah algoritma pengurutan data yang bekerja dengan membangun subarray terurut satu elemen pada satu waktu. Hal ini dilakukan dengan mengambil elemen dari bagian array yang belum diurut.

Setelah itu, insertion sort akan menempatkannya pada posisi sesuai di dalam sub-array yang sudah terurut. Proses ini akan diulang hingga tidak ada lagi elemen tersisa di bagian yang belum diurut.

Cara Kerja Insertion Sort

Berikut adalah beberapa langkah yang menggambarkan cara kerja insertion sort:

Mulai proses pengurutan dari elemen kedua dengan asumsi bagian pertama sudah berada di sub-array terurut.
Ambil elemen berikutnya dari bagian yang belum diurut dan simpan sebagai key (bagian yang ditempatkan pada posisi tepat di sub-array terurut).
Bandingkan key dengan elemen-elemen di sub-array yang telah terurut dari belakang ke depan.
Ulangi langkah sebelumnya hingga menemukan posisi di mana key lebih besar atau sama dengan elemen di sub array atau hingga mencapai awal array.
Ulangi proses tersebut hingga seluruh array diurutkan.

Kelebihan dan Kekurangan Insertion Sort

Insertion sort adalah algoritma pengurutan yang cukup sederhana dan intuitif. Meski begitu, insertion sort memiliki kelebihan dan kekurangan yang harus dipertimbangkan. Berikut adalah beberapa kelebihan dan kekurangannya:

Kelebihan Insertion Sort

Berikut adalah beberapa kelebihan insertion sort yang merupakan keunggulannya:

Sederhana dan Mudah Dipahami: Algoritma insertion sort sangat sederhana untuk dipahami dan diimplementasikan. Ini menjadikannya pilihan yang baik untuk pendidikan dan penggunaan dalam skenario sederhana.
Efektif untuk Data Set Kecil: Insertion sort sangat efisien untuk data set yang kecil, terutama jika data set tersebut sudah hampir terurut.
Stable: Insertion sort adalah stable sort. Artinya, dua elemen dengan nilai kunci yang sama akan mempertahankan urutan relatif mereka setelah pengurutan.
In-Place: Insertion sort tidak memerlukan alokasi memori tambahan yang signifikan.
Online: Insertion sort dapat bekerja sebagai algoritma pengurutan online.

Kekurangan Insertion Sort

Berikut adalah beberapa kekurangan insertion sort yang harus dipertimbangkan:

Tidak Efisien untuk Data Set Besar: Kompleksitas waktu algoritma ini membuatnya tidak efisien untuk mengurutkan data set besar.
Banyak Operasi Swap dan Perbandingan: Untuk elemen yang harus dipindahkan ke dekat awal array, insertion sort memerlukan banyak operasi swap dan perbandingan. Hal ini dapat mengurangi efisiensinya.
Sensitif terhadap Urutan Input: Meskipun efektif untuk data yang hampir terurut, ini membuatnya tidak efisien jika elemen-elemen pada awalnya terurut dalam urutan terbalik. Ini memerlukan jumlah perbandingan dan perpindahan maksimum.

Implementasi Insertion Sort

Untuk memahami insertion sort secara lebih dalam, MinDi siapkan contoh implementasi kodenya. Implementasi insertion sort ini digunakan untuk mengurutkan array [5, 6, 11, 12, 13] menjadi [12, 11, 13, 5, 6].

Berikut adalah kode Python untuk implementasi tersebut:

Demikian penjelasan lengkap mengenai apa itu insertion sort hingga implementasinya. Penjelasan di atas menunjukkan bahwa insertion sort adalah salah satu algoritma sederhana yang mudah diimplementasikan.

Meski begitu, ini kurang cocok digunakan untuk data set dalam jumlah besar. Untuk mengolah data dalam jumlah besar, kamu mungkin perlu menggunakan metode lainnya. Tertarik untuk mempelajarinya?

Bagi yang tertarik, MinDi rekomendasikanmu untuk ikut Bootcamp Data Science Dibimbing.id. Program ini cocok buat kamu yang mau belajar data science dari nol hingga mahir.

Pembelajarannya lengkap dan didasari oleh silabus beginner-friendly. Kamu bisa belajar konsep dasar, teori, aplikasi data, tools, hingga praktik dengan real-case project. Intinya, kamu bakal dibimbing sampai jadi!

So, segera gabung dan mulai karirmu di data science bareng Dibimbing.id!