Pengurutan dapat membantu kita untuk mencari, menyimpan, atau memproses data dengan lebih mudah dan efisien. Ada banyak algoritma pengurutan yang berbeda-beda, salah satunya adalah Insertion Sort.
Apa itu 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.
Bagaimana Cara Kerja Insertion Sort?
Insertion Sort bekerja dengan cara membagi list menjadi dua bagian, yaitu bagian yang sudah diurutkan dan bagian yang belum diurutkan. Pada awalnya, hanya elemen pertama saja yang dianggap sudah diurutkan, sedangkan sisanya masih belum diurutkan. Kemudian, elemen kedua diambil dari bagian yang belum diurutkan dan disisipkan ke posisi yang tepat pada bagian yang sudah diurutkan. Proses ini berulang sampai semua elemen terurut.
Berikut adalah contoh langkah-langkah insertion sort untuk mengurutkan list [5, 2, 4, 6, 1, 3] dari kecil ke besar:
- List awal: [5, 2, 4, 6, 1, 3]. Elemen pertama (5) dianggap sudah diurutkan.
- Ambil elemen kedua (2) dan bandingkan dengan elemen pertama (5). Karena 2 lebih kecil dari 5, maka geser 5 ke kanan dan sisipkan 2 ke posisi pertama. List sekarang: [2, 5, 4, 6, 1, 3].
- Ambil elemen ketiga (4) dan bandingkan dengan elemen kedua (5). Karena 4 lebih kecil dari 5, maka geser 5 ke kanan dan bandingkan 4 dengan elemen pertama (2). Karena 4 lebih besar dari 2, maka sisipkan 4 di antara 2 dan 5. List sekarang: [2, 4, 5, 6, 1, 3].
- Ambil elemen keempat (6) dan bandingkan dengan elemen ketiga (5). Karena 6 lebih besar dari 5, maka tidak perlu menggeser atau menyisipkan apa pun. List sekarang: [2, 4, 5, 6, 1, 3].
- Ambil elemen kelima (1) dan bandingkan dengan elemen keempat (6). Karena 1 lebih kecil dari 6, maka geser 6 ke kanan dan bandingkan 1 dengan elemen ketiga (5). Karena 1 lebih kecil dari 5, maka geser 5 ke kanan dan bandingkan 1 dengan elemen kedua (4). Karena 1 lebih kecil dari 4, maka geser 4 ke kanan dan bandingkan 1 dengan elemen pertama (2). Karena 1 lebih kecil dari 2, maka geser 2 ke kanan dan sisipkan 1 ke posisi pertama. List sekarang: [1, 2, 4, 5, 6, 3].
- Ambil elemen keenam (3) dan bandingkan dengan elemen kelima (6). Karena
3 lebih kecil dari 6, maka geser 6 ke kanan dan bandingkan 3 dengan elemen keempat (5). Karena 3 lebih kecil dari 5, maka geser 5 ke kanan dan bandingkan 3 dengan elemen ketiga (4). Karena 3 lebih kecil dari 4, maka geser 4 ke kanan dan bandingkan 3 dengan elemen kedua (2). Karena 3 lebih besar dari 2, maka sisipkan 3 di antara 2 dan 4. List sekarang: [1, 2, 3, 4, 5, 6].
List sudah terurut sepenuhnya.
Apa Kelebihan dan Kekurangan Insertion Sort?
Insertion Sort memiliki beberapa kelebihan dan kekurangan, yaitu:
- Kelebihan:
- Algoritma yang sederhana dan mudah dipahami.
- Efisien untuk list yang sudah hampir terurut atau memiliki jumlah elemen yang sedikit.
- Stabil, artinya tidak mengubah posisi elemen yang sama.
- In-place, artinya tidak membutuhkan memori tambahan selain list itu sendiri.
- Kekurangan:
- Kompleksitas waktu yang buruk untuk list dengan jumlah elemen yang besar. Algoritma ini membutuhkan waktu O(n2) di kasus terburuk dan rata-rata, di mana n adalah jumlah elemen list.
- Sangat sensitif terhadap urutan awal list. Jika list sudah terurut, maka algoritma ini hanya membutuhkan waktu O(n), tetapi jika list terurut terbalik, maka algoritma ini akan membutuhkan waktu paling lama.
Kesimpulan
Insertion Sort adalah proses mengurutkan sebuah list dengan cara menyisipkan elemen satu per satu sesuai urutan besar kecilnya. Algoritma ini memiliki kelebihan dan kekurangan yang perlu dipertimbangkan sebelum menggunakannya. Insertion Sort cocok untuk list yang sudah hampir terurut atau memiliki jumlah elemen yang sedikit, tetapi tidak cocok untuk list dengan jumlah elemen yang besar atau terurut terbalik.
Semoga artikel ini bermanfaat untuk Anda. Jika Anda memiliki pertanyaan atau saran, silakan tinggalkan komentar di bawah. Terima kasih telah membaca.
