Algoritma Insertion Sort: Pengertian, Cara Kerja dan Implementasi

Algoritma Insertion Sort adalah salah satu algoritma pengurutan sederhana yang digunakan dalam pemrograman. Meskipun tidak seefisien beberapa algoritma pengurutan lainnya, seperti Merge Sort atau Quick Sort, Insertion Sort sangat mudah dipahami dan diimplementasikan, menjadikannya pilihan yang baik untuk dataset kecil atau untuk pengajaran konsep dasar pengurutan.

Artikel ini kita akan membahas Algoritma Insertion Sort secara mendalam, termasuk cara kerjanya, implementasinya dalam berbagai bahasa pemrograman, serta kelebihan dan kekurangannya.

Apa Itu Algoritma Insertion Sort?

Algoritma adalah urutan langkah-langkah logis untuk menyelesaikan sebuah masalah atau tugas tertentu. Algoritma sering digunakan dalam pemrograman komputer, tetapi juga bisa digunakan dalam banyak konteks lainnya.

Algoritma Insertion Sort bekerja dengan cara membangun array yang diurutkan satu per satu dengan mengambil elemen dari array yang belum diurutkan dan menyisipkannya ke posisi yang benar dalam array yang sudah diurutkan. Proses ini mirip dengan cara seseorang menyusun kartu di tangan saat bermain kartu, dengan setiap kartu baru ditempatkan di posisi yang benar relatif terhadap kartu yang sudah ada di tangan.

Cara Kerja Algoritma Insertion Sort

Berikut adalah langkah-langkah dasar cara kerja dari Algoritma ini:

1. Mulai dari Elemen Kedua: Anggap elemen pertama dari array sebagai sudah diurutkan. Mulai dari elemen kedua, bandingkan dengan elemen sebelumnya untuk menentukan posisi yang tepat.
2. Bandingkan dan Sisipkan: Bandingkan elemen saat ini dengan elemen sebelumnya di array yang sudah diurutkan. Jika elemen saat ini lebih kecil, geser elemen sebelumnya satu posisi ke kanan dan lanjutkan perbandingan ke belakang hingga menemukan posisi yang tepat.
3. Sisipkan Elemen: Setelah menemukan posisi yang tepat, sisipkan elemen saat ini di posisi tersebut.
4. Ulangi Proses: Ulangi proses ini untuk semua elemen dalam array sampai seluruh array terurut.

Contoh Langkah demi Langkah

Misalkan kita memiliki array yang tidak terurut: [5, 2, 9, 1, 5, 6].

1. Langkah 1: Anggap elemen pertama [5] sudah terurut.
2. Langkah 2: Bandingkan elemen kedua 2 dengan 5. Karena 2 lebih kecil dari 5, geser 5 ke kanan dan sisipkan 2 di posisi pertama. Array menjadi [2, 5, 9, 1, 5, 6].
3. Langkah 3: Bandingkan elemen ketiga 9 dengan 5. Karena 9 lebih besar dari 5, biarkan di tempatnya. Array tetap [2, 5, 9, 1, 5, 6].
4. Langkah 4: Bandingkan elemen keempat 1 dengan 9, 5 dan 2. Karena 1 lebih kecil dari semuanya, geser 9, 5 dan 2 ke kanan dan sisipkan 1 di posisi pertama. Array menjadi [1, 2, 5, 9, 5, 6].
5. Langkah 5: Bandingkan elemen kelima 5 dengan 9. Karena 5 lebih kecil dari 9, geser 9 ke kanan dan sisipkan 5 di posisi yang tepat. Array menjadi [1, 2, 5, 5, 9, 6].
6. Langkah 6: Bandingkan elemen keenam 6 dengan 9. Karena 6 lebih kecil dari 9, geser 9 ke kanan dan sisipkan 6 di posisi yang tepat. Array menjadi [1, 2, 5, 5, 6, 9].

Implementasi Algoritma Insertion Sort

Implementasi dalam JavaScript

Berikut adalah contoh implementasi dalam bahasa pemrograman JavaScript:

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

let arr = [5, 2, 9, 1, 5, 6];
console.log("Array yang sudah diurutkan:", insertionSort(arr));

Implementasi dalam Python

Berikut adalah contoh implementasi dalam bahasa pemrograman 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

arr = [5, 2, 9, 1, 5, 6]
insertion_sort(arr)
print("Array yang sudah diurutkan:", arr)

Kompleksitas Waktu dan Ruang

Kompleksitas waktu dan ruang adalah faktor penting dalam menentukan efisiensi suatu algoritma. Untuk Insertion Sort, berikut adalah analisis kompleksitasnya:

Kompleksitas Waktu

• Kasus Terbaik: O(n) – Terjadi ketika daftar sudah terurut. Algoritma hanya perlu satu perbandingan untuk setiap elemen.
• Kasus Rata-rata: O(n^2) – Terjadi ketika elemen-elemen dalam daftar diurutkan secara acak.
• Kasus Terburuk: O(n^2) – Terjadi ketika daftar diurutkan secara terbalik. Setiap elemen harus dibandingkan dengan semua elemen sebelumnya.

Kompleksitas Ruang

• Ruang Tambahan: O(1) – Insertion Sort adalah algoritma pengurutan in-place, yang berarti tidak memerlukan ruang tambahan selain beberapa variabel tambahan untuk penyimpanan sementara.

Kelebihan dan Kekurangan Insertion Sort

Kelebihan Insertion Sort

1. Sederhana dan Mudah Dipahami: Algoritma ini sangat mudah dipahami dan diimplementasikan, menjadikannya alat pengajaran yang baik untuk konsep pengurutan.
2. Efisien untuk Dataset Kecil: Insertion Sort dapat sangat efisien untuk dataset yang kecil atau hampir terurut.
3. In-place Sorting: Algoritma ini tidak memerlukan ruang tambahan yang signifikan, karena pengurutan dilakukan di tempat.
4. Stabilitas: Insertion Sort adalah algoritma pengurutan yang stabil, yang berarti elemen dengan nilai yang sama akan mempertahankan urutan relatif mereka.

Kekurangan Insertion Sort

1. Tidak Efisien untuk Dataset Besar: Kompleksitas waktu O(n^2) membuat Insertion Sort tidak efisien untuk dataset yang besar.
2. Performa Tergantung pada Urutan Data Awal: Algoritma ini bekerja sangat baik pada data yang hampir terurut, tetapi performanya menurun drastis jika data sangat tidak terurut.

Penerapan Insertion Sort dalam Dunia Nyata

Meskipun Insertion Sort tidak digunakan secara luas dalam aplikasi yang memerlukan pengurutan dataset besar, ada beberapa situasi di mana algoritma ini sangat berguna:

1. Pengurutan Dataset Kecil: Dalam situasi di mana dataset kecil perlu diurutkan, Insertion Sort bisa sangat cepat dan sederhana untuk diterapkan.
2. Algoritma Kombinasi: Dalam beberapa kasus, Insertion Sort digunakan bersama dengan algoritma pengurutan lain. Misalnya, Quick Sort atau Merge Sort dapat beralih ke Insertion Sort untuk subarray kecil untuk meningkatkan performa.
3. Pengurutan Langsung: Ketika data datang dalam aliran kontinu dan perlu diurutkan seiring dengan kedatangannya, Insertion Sort dapat digunakan karena mampu menangani penambahan data secara inkremental.

Kesimpulan

Pada pembahasan kita di atas dapat kita simpulkan bahwa Algoritma Insertion Sort adalah salah satu algoritma pengurutan dasar yang penting untuk dipahami. Meskipun memiliki keterbatasan dalam hal efisiensi untuk dataset besar, kesederhanaan dan stabilitasnya membuatnya menjadi pilihan yang baik untuk situasi tertentu, terutama ketika berhadapan dengan dataset kecil atau hampir terurut.

Memahami Insertion Sort juga membantu dalam memahami prinsip dasar pengurutan yang digunakan dalam algoritma yang lebih kompleks. Dengan implementasi yang mudah dan konsep yang jelas, Insertion Sort tetap relevan dalam dunia pemrograman dan ilmu komputer.

Dengan pemahaman mendalam tentang cara kerja, implementasi, kelebihan dan kekurangan Insertion Sort, kamu akan dapat menggunakan algoritma ini dengan tepat dan mengerti kapan harus memilih algoritma pengurutan lainnya yang lebih sesuai untuk kebutuhan tertentu.

Artikel ini merupakan bagian seri artikel Programming dari KantinIT.com dan jika ada ide topik yang mau kami bahas silahkan komen di bawah ya..