Insertion Sort di C++: Pengertian, Cara Kerja, dan Contoh Program

Dalam dunia pemrograman, mengurutkan data adalah salah satu tugas yang sering dihadapi oleh programmer. Ada banyak algoritma sorting yang bisa digunakan, dan salah satunya adalah Insertion Sort. Artikel ini akan membahas secara lengkap tentang Insertion Sort di C++, mulai dari pengertian, mekanisme kerja, hingga contoh programnya.

Insertion Sort di C++

Pengertian Insertion Sort

Insertion Sort adalah salah satu teknik sorting dalam ilmu komputer yang menggunakan pendekatan secara iteratif. Dalam Insertion Sort, elemen data diurutkan satu per satu, berbeda dengan teknik lain seperti Bubble Sort yang melakukan perbandingan antara dua elemen data dalam satu iterasi.

Cara Kerja Insertion Sort di C++

Mekanisme kerja dari Insertion Sort cukup sederhana. Pertama-tama, algoritma ini akan memilih satu elemen dari array dan membandingkannya dengan elemen sebelumnya. Jika elemen sebelumnya lebih besar, maka elemen tersebut akan dipindahkan ke posisi yang benar dalam array yang sudah diurutkan sebelumnya.

Langkah-langkah Cara Kerja:

1. Ambil elemen pertama dari array yang belum diurutkan.
2. Bandingkan dengan elemen-elemen pada array yang sudah diurutkan.
3. Jika elemen tersebut lebih kecil, pindahkan elemen tersebut ke posisi yang sesuai pada array yang sudah diurutkan.
4. Ulangi langkah 1-3 hingga semua elemen pada array yang belum diurutkan dipindahkan ke array yang sudah diurutkan.

Baca Juga: Tutorial Lengkap Belajar Bahasa Pemrograman C++

Contoh Program Insertion Sort di C++

Untuk memahami Insertion Sort di C++ lebih dalam, mari kita bahas contoh programnya. Program ini terdiri dari dua fungsi utama: insertionSort() dan main(). Berikut adalah program lengkapnya dalam satu bagian:

#include <iostream>

using namespace std;

void insertionSort(int arr[], int n) {

    for (int i = 1; i < n; i++) {

        int key = arr[i];

        int j = i - 1;

        while (j >= 0 && arr[j] > key) {

            arr[j + 1] = arr[j];

            j--;

        }

        arr[j + 1] = key;

    }

}

int main() {

    int arr[] = {12, 11, 13, 5, 6};

    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    for (int i = 0; i < n; i++) {

        cout << arr[i] << " ";

    }

    return 0;

}

Output

5 6 11 12 13

Penjelasan Program

Header dan Namespace

Program dimulai dengan #include <iostream>, yang merupakan header untuk melakukan operasi input dan output. Kemudian, menggunakan namespace std agar kita tidak perlu mengetik std:: sebelum setiap fungsi dari pustaka standar.

Fungsi insertionSort

Fungsi insertionSort() adalah jantung dari program ini. Fungsi ini menerima array arr[] dan panjang n dari array sebagai parameter.

• Loop Pertama (for (int i = 1; i < n; i++)): Iterasi dimulai dari indeks ke-1 (bukan 0) karena kita menganggap elemen pada indeks ke-0 sudah diurutkan.
• Inisialisasi key (int key = arr[i]): key digunakan untuk menyimpan nilai dari elemen yang akan kita bandingkan.
• Loop Kedua (while (j >= 0 && arr[j] > key)): Loop ini digunakan untuk membandingkan key dengan elemen-elemen di subarray yang sudah diurutkan. Jika arr[j] > key, kita geser elemen tersebut satu posisi ke kanan.
• Penyisipan (arr[j + 1] = key): Setelah loop kedua, kita letakkan key pada posisi yang benar di dalam array yang sudah diurutkan.

Fungsi main

• Inisialisasi Array (int arr[] = {12, 11, 13, 5, 6}): Di sini, kita mendefinisikan array arr yang akan diurutkan.
• Memanggil Fungsi (insertionSort(arr, n)): Fungsi insertionSort dipanggil untuk melakukan sorting.
• Output Hasil (cout << arr[i] << " "): Menampilkan elemen-elemen array yang telah diurutkan.

Kelebihan dan Kekurangan Insertion Sort

Kelebihan Insertion Sort:

• Sederhana dan Mudah Diimplementasikan: Insertion Sort adalah algoritma yang sederhana dan kode programnya cukup mudah untuk diimplementasikan. Ini menjadikannya pilihan yang baik untuk programmer pemula.
• Efisien untuk Data Kecil: Untuk kumpulan data yang kecil, Insertion Sort bisa lebih cepat daripada algoritma sorting lainnya seperti Quick Sort atau Merge Sort.
• Stabil: Insertion Sort adalah algoritma yang stabil, yang berarti bahwa dua objek dengan nilai kunci yang sama akan tetap mempertahankan urutan relatif mereka bahkan setelah pengurutan. 
• Memori Efisien: Algoritma ini mengurutkan data "in-place", yaitu tanpa membutuhkan memori tambahan.
• Adaptif: Insertion Sort adalah algoritma yang adaptif, artinya semakin mendekati urutan, semakin cepat algoritma ini akan bekerja.

Kekurangan Insertion Sort:

• Tidak Efisien untuk Data Besar: Insertion Sort memiliki kompleksitas waktu O(n^2), yang membuatnya kurang efisien untuk kumpulan data yang besar.
• Banyak Operasi Swap: Dalam kasus terburuk, Insertion Sort bisa melakukan banyak operasi swap, yang bisa mempengaruhi performa.
• Kurang Efisien Dibandingkan Algoritma Lain: Ketika dibandingkan dengan algoritma sorting yang lebih canggih seperti Quick Sort atau Merge Sort, Insertion Sort kurang efisien dalam hal kecepatan.

Algoritma Insertion Sort adalah salah satu algoritma sorting yang paling dasar dan mudah diimplementasikan, khususnya dalam bahasa pemrograman seperti C++. Melalui artikel ini, diharapkan Anda mendapatkan pemahaman yang lebih baik tentang Insertion Sort di C++, baik dari segi teori maupun implementasinya.

Daftar Pustaka

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2021). Introduction to Algorithms (4th ed.). The MIT Press.
• Sedgewick, R., & Wayne, K. (2019). Algorithms (4th ed.). Addison-Wesley.

Semoga artikel ini memberikan informasi yang lengkap, detail, dan mudah dipahami mengenai Insertion Sort di C++. Selamat mencoba!

MateriDosen.Com

Berbagi: