Insertion Sort: Memahami dan Menguasai Algoritma Pengurutan Sederhana
Insertion Sort, atau pengurutan sisip, merupakan salah satu algoritma pengurutan yang paling sederhana dan intuitif untuk dipahami. Meskipun efisiensinya tidak sebanding dengan algoritma pengurutan yang lebih canggih seperti Merge Sort atau Quick Sort, Insertion Sort memiliki keunggulan dalam kesederhanaan implementasi dan efektivitasnya pada dataset yang kecil atau hampir terurut. Algoritma ini bekerja dengan membangun array yang terurut secara bertahap, satu elemen pada satu waktu. Konsepnya mirip dengan cara kita mengurutkan kartu remi di tangan. Kita mengambil satu kartu (elemen) dan menyisipkannya ke posisi yang tepat di antara kartu-kartu lain yang sudah terurut.
Bagaimana Insertion Sort Bekerja: Analogia Kartu Remi
Bayangkan Anda sedang mengurutkan kartu remi di tangan Anda. Anda memegang kartu-kartu yang sudah terurut di tangan kiri, dan kartu-kartu yang belum terurut di tangan kanan. Untuk setiap kartu di tangan kanan, Anda membandingkannya dengan kartu-kartu di tangan kiri, mulai dari kartu paling kanan hingga kartu paling kiri. Jika kartu di tangan kanan lebih kecil dari kartu di tangan kiri, Anda menggeser kartu di tangan kiri ke kanan untuk memberi ruang bagi kartu di tangan kanan. Proses ini berlanjut hingga Anda menemukan posisi yang tepat untuk kartu di tangan kanan, lalu Anda menyisipkannya ke posisi tersebut.
Algoritma Insertion Sort meniru proses ini pada array. Secara iteratif, algoritma ini mengambil satu elemen dari bagian array yang belum terurut dan menempatkannya pada posisi yang tepat di bagian array yang sudah terurut.
Langkah-Langkah Implementasi Insertion Sort:
Mari kita bedah langkah-langkah implementasi Insertion Sort dengan lebih detail. Misalkan kita memiliki array berikut: [5, 2, 4, 6, 1, 3]
.
-
Iterasi Pertama (i = 1):
- Elemen yang akan disisipkan adalah
arr[1]
yaitu2
. - Bandingkan
2
denganarr[0]
yaitu5
. Karena2 < 5
, geser5
ke kanan. - Sisipkan
2
ke posisiarr[0]
. Array sekarang menjadi:[2, 5, 4, 6, 1, 3]
.
- Elemen yang akan disisipkan adalah
-
Iterasi Kedua (i = 2):
- Elemen yang akan disisipkan adalah
arr[2]
yaitu4
. - Bandingkan
4
denganarr[1]
yaitu5
. Karena4 < 5
, geser5
ke kanan. - Bandingkan
4
denganarr[0]
yaitu2
. Karena4 > 2
, sisipkan4
ke posisiarr[1]
. Array sekarang menjadi:[2, 4, 5, 6, 1, 3]
.
- Elemen yang akan disisipkan adalah
-
Iterasi Ketiga (i = 3):
- Elemen yang akan disisipkan adalah
arr[3]
yaitu6
. - Bandingkan
6
denganarr[2]
yaitu5
. Karena6 > 5
, tidak perlu menggeser. Sisipkan6
ke posisiarr[3]
. Array sekarang menjadi:[2, 4, 5, 6, 1, 3]
.
- Elemen yang akan disisipkan adalah
-
Iterasi Keempat (i = 4):
- Elemen yang akan disisipkan adalah
arr[4]
yaitu1
. - Bandingkan
1
denganarr[3]
yaitu6
. Karena1 < 6
, geser6
ke kanan. - Bandingkan
1
denganarr[2]
yaitu5
. Karena1 < 5
, geser5
ke kanan. - Bandingkan
1
denganarr[1]
yaitu4
. Karena1 < 4
, geser4
ke kanan. - Bandingkan
1
denganarr[0]
yaitu2
. Karena1 < 2
, geser2
ke kanan. - Sisipkan
1
ke posisiarr[0]
. Array sekarang menjadi:[1, 2, 4, 5, 6, 3]
.
- Elemen yang akan disisipkan adalah
-
Iterasi Kelima (i = 5):
- Elemen yang akan disisipkan adalah
arr[5]
yaitu3
. - Bandingkan
3
denganarr[4]
yaitu6
. Karena3 < 6
, geser6
ke kanan. - Bandingkan
3
denganarr[3]
yaitu5
. Karena3 < 5
, geser5
ke kanan. - Bandingkan
3
denganarr[2]
yaitu4
. Karena3 < 4
, geser4
ke kanan. - Bandingkan
3
denganarr[1]
yaitu2
. Karena3 > 2
, sisipkan3
ke posisiarr[2]
. Array sekarang menjadi:[1, 2, 3, 4, 5, 6]
.
- Elemen yang akan disisipkan adalah
Setelah semua iterasi selesai, array akan terurut: [1, 2, 3, 4, 5, 6]
.
Kode Implementasi (Python):
Berikut adalah contoh kode implementasi Insertion Sort dalam bahasa Python:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# Contoh penggunaan
arr = [5, 2, 4, 6, 1, 3]
sorted_arr = insertion_sort(arr)
print(sorted_arr) # Output: [1, 2, 3, 4, 5, 6]
Analisis Kompleksitas Waktu:
- Best Case (Array sudah terurut): O(n) – Hanya melakukan satu perbandingan untuk setiap elemen.
- Average Case (Array acak): O(n^2) – Melakukan perbandingan dan pergeseran rata-rata untuk setiap elemen.
- Worst Case (Array terurut terbalik): O(n^2) – Melakukan perbandingan dan pergeseran maksimal untuk setiap elemen.
Karena kompleksitas waktu kuadratiknya, Insertion Sort tidak cocok untuk dataset yang sangat besar.
Keunggulan dan Kekurangan:
Keunggulan:
- Sederhana dan Mudah Diimplementasikan: Kode relatif pendek dan mudah dipahami.
- Efisien untuk Dataset Kecil atau Hampir Terurut: Lebih cepat daripada algoritma kompleks lainnya untuk dataset dengan ukuran kecil atau yang sudah hampir terurut.
- In-Place Sorting: Tidak memerlukan ruang memori tambahan yang signifikan (hanya membutuhkan ruang konstan).
- Stable Sorting: Mempertahankan urutan relatif elemen-elemen dengan nilai yang sama.
- Online Sorting: Dapat mengurutkan data secara real-time saat data tiba.
Kekurangan:
- Tidak Efisien untuk Dataset Besar: Kompleksitas waktu kuadratik membuatnya tidak praktis untuk dataset dengan ukuran besar.
- Performa Buruk dibandingkan Algoritma Lain: Algoritma pengurutan lain seperti Merge Sort dan Quick Sort memiliki performa yang jauh lebih baik untuk dataset besar.
Kapan Menggunakan Insertion Sort?
Meskipun memiliki keterbatasan, Insertion Sort masih relevan dalam beberapa skenario:
- Dataset dengan Ukuran Kecil: Ketika jumlah data yang perlu diurutkan relatif kecil (misalnya, kurang dari 50 elemen), Insertion Sort dapat menjadi pilihan yang baik karena kesederhanaannya.
- Dataset Hampir Terurut: Jika data sudah hampir terurut, Insertion Sort akan bekerja dengan sangat cepat karena hanya perlu melakukan sedikit perbandingan dan pergeseran.
- Digunakan sebagai Bagian dari Algoritma Hybrid: Beberapa algoritma pengurutan yang lebih canggih, seperti IntroSort, menggunakan Insertion Sort untuk mengurutkan sub-array kecil setelah proses partisi awal.
- Saat Ruang Memori Terbatas: Karena merupakan algoritma in-place, Insertion Sort ideal jika ruang memori terbatas.
- Online Sorting: Saat data terus berdatangan dan perlu diurutkan secara real-time.
Kesimpulan:
Insertion Sort merupakan algoritma pengurutan yang sederhana dan mudah dipahami, namun memiliki keterbatasan dalam hal efisiensi untuk dataset besar. Keunggulannya terletak pada kesederhanaan implementasi, efektivitasnya pada dataset kecil atau hampir terurut, dan sifatnya yang in-place dan stable. Memahami Insertion Sort merupakan langkah penting dalam mempelajari algoritma pengurutan yang lebih kompleks. Pertimbangkan baik-baik ukuran dan karakteristik data Anda sebelum memutuskan apakah Insertion Sort adalah algoritma yang tepat untuk digunakan. Jika Anda memiliki dataset besar, algoritma lain seperti Merge Sort atau Quick Sort mungkin lebih sesuai. Namun, untuk skenario tertentu, Insertion Sort tetap menjadi alat yang berguna dan efisien dalam kotak peralatan pengurutan Anda.