Latihan C++ #42: Membuat Insertion Sort

Anak Males –  Artikel ini akan memberikan cara untuk membuat sebuah program dengan bahasa C++ yang mengaplikasikan pengurutan insertion sort.

Insertion sort adalah algoritma sorting yang beroperasi dengan cara menyisipkan elemen ke dalam posisi yang tepat dari sebuah array yang sudah diurutkan.

Algoritma ini dianggap sebagai salah satu metode yang paling sederhana untuk melakukan sorting.

Dalam implementasi C++, insertion sort dapat dilakukan dengan menggunakan beberapa loop dan perbandingan elemen.

Artikel ini akan menjelaskan bagaimana cara kerja algoritma insertion sort dan bagaimana melakukan implementasi dalam bahasa C++.

Baca : Latihan C++ #41: Membuat Deret Angka

Algoritma Insertion Sort

Insertion sort adalah algoritma sorting yang beroperasi dengan cara menyisipkan elemen ke dalam posisi yang tepat dari sebuah array yang sudah diurutkan. Algoritma ini bekerja dengan membandingkan elemen satu per satu dengan elemen yang sudah diurutkan sebelumnya, dan menyisipkannya ke dalam posisi yang tepat.

Proses pengurutan dimulai dari indeks ke-1 dari array. Elemen pertama dianggap sudah diurutkan. Kemudian, elemen kedua dibandingkan dengan elemen pertama, dan jika elemen kedua lebih kecil, elemen kedua akan ditukar dengan elemen pertama. Proses ini dilanjutkan dengan elemen ketiga, keempat, dan seterusnya, sampai semua elemen diurutkan dengan benar.

Secara umum, algoritma Insertion Sort terdiri dari dua bagian utama:

• Bagian pembandingan, dimana elemen akan dibandingkan dengan elemen-elemen yang sudah diurutkan sebelumnya.
• Bagian penyisipan, dimana elemen akan disisipkan ke dalam posisi yang tepat dari array yang sudah diurutkan.

Insertion sort adalah algoritma yang sangat cocok untuk digunakan pada data yang sudah hampir terurut, karena dalam kondisi tersebut, algoritma ini dapat menyelesaikan pengurutan dengan cepat. Namun, dalam kondisi dimana data awalnya sangat acak, algoritma ini dapat menjadi sangat lambat.

Implementasi algoritma insertion sort dalam bahasa C++ dapat dilakukan dengan menggunakan loop for dan perbandingan elemen menggunakan operator perbandingan seperti < atau >.

Dalam implementasi ini, elemen akan dibandingkan satu per satu dan disisipkan ke dalam posisi yang tepat dari array yang sudah diurutkan.

Baca : Latihan C++ #40: Membuat Merge Sort

Program C++ Membuat  Insertion Sort

Berikut ini adalah contoh program C++ untuk melakukan sorting dengan menggunakan algoritma Insertion Sort dan inputan yang diambil dari user:

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i-1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j = j-1;
        }
        arr[j+1] = key;
    }
}

int main() {
    int n, i;
    cout << "Masukkan jumlah elemen yang akan diurutkan: ";
    cin >> n;
    int arr[n];
    cout << "Masukkan elemen yang akan diurutkan: ";
    for (i = 0; i < n; i++) {
        cin >> arr[i];
    }
    insertionSort(arr, n);
    cout << "Hasil akhir setelah diurutkan: \n";
    for (i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

Berikut adalah penjelasan lebih detail tentang masing-masing bagian dari kode program di atas:

#include <iostream> : statement ini digunakan untuk meng-include library iostream yang digunakan untuk mengakses input output seperti cin dan cout.

using namespace std; : statement ini digunakan untuk menggunakan namespace standar dari C++.

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i-1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j = j-1;
        }
        arr[j+1] = key;
    }
}

statement ini digunakan untuk mendeklarasikan fungsi insertionSort dengan parameter arr sebagai array yang akan diurutkan dan n sebagai jumlah elemen dari array tersebut. Fungsi ini menggunakan loop for dan while untuk mengeksekusi proses pengurutan.

int main() {
    int n, i;
    cout << "Masukkan jumlah elemen yang akan diurutkan: ";
    cin >> n;
    int arr[n];
    cout << "Masukkan elemen yang akan diurutkan: ";
    for (i = 0; i < n; i++) {
        cin >> arr[i];
    }

statement ini digunakan untuk mendeklarasikan fungsi utama dari program dan mengambil input dari user berupa jumlah elemen yang akan diurutkan dan setiap elemen yang akan diurutkan. Kemudian program akan memanggil fungsi insertionSort() untuk mengurutkan elemen.

insertionSort(arr, n); : statement ini digunakan untuk memanggil fungsi insertionSort yang telah dideklarasikan sebelumnya dengan parameter arr sebagai array yang akan diurutkan dan n sebagai jumlah elemen dari array tersebut.

Baca : Latihan C++ #39 : Membuat Quick Sort

cout << "Hasil akhir setelah diurutkan: \n";
    for (i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

statement ini digunakan untuk menampilkan hasil akhir setelah diurutkan.

return 0; : statement ini digunakan untuk mengakhiri program dan mengembalikan nilai 0.

Output Program C++ Membuat  Insertion Sort

Berikut ini adalah contoh output dari program C++ Insertion Sort yang menggunakan input dari user:

Masukkan jumlah elemen yang akan diurutkan: 5
Masukkan elemen yang akan diurutkan: 4 2 3 1 5
Hasil akhir setelah diurutkan: 
1 2 3 4 5

Baca : Latihan C++ #23 : Program C++ Pembalik Angka Rekursif

Dalam contoh di atas, program meminta input dari user berupa jumlah elemen yang akan diurutkan (5) dan setiap elemen yang akan diurutkan (4, 2, 3, 1, 5).

Kemudian program akan menjalankan proses pengurutan dengan menggunakan algoritma Insertion Sort dan menampilkan hasil akhir setelah diurutkan, yaitu 1, 2, 3, 4, 5.

Penutup

Sekian untuk tutorial C++ kali ini, sampai jumpa di tutorial C++ lainnya.