Latihan kode program C++ kali ini akan membahas cara mengurutkan angka menggunakan algoritma insertion sort. Algoritma sorting banyak dipakai dalam pembahasan materi algoritma dasar di kampus-kampus IT.
Soal Mengurutkan Angka dengan Algoritma Insertion Sort
Buatlah kode program C++ untuk mengurutkan angka menggunakan algoritma insertion sort. Program meminta 1 nilai input untuk menentukan jumlah angka yang akan diurutkan, kemudian user memasukkan angka tersebut satu per satu. Setelah itu program menampilkan hasil urutan dari nilai terkecil ke terbesar (ascending).
Soal bonus: buat juga dalam bentuk function.
Berikut contoh tampilan akhir yang diinginkan (1):
## Program C++ Mengurutkan Angka (Insertion Sort) ## ===================================================== Input jumlah element array: 6 Input 6 angka (dipisah dengan enter): Angka ke-1: 23 Angka ke-2: 54 Angka ke-3: 76 Angka ke-4: 12 Angka ke-5: 87 Angka ke-6: 45 Array setelah diurutkan: 12 23 45 54 76 87
Berikut contoh tampilan akhir yang diinginkan (2):
## Program C++ Mengurutkan Angka (Insertion Sort) ## ===================================================== Input jumlah element array: 8 Input 8 angka (dipisah dengan enter): Angka ke-1: 111 Angka ke-2: 456 Angka ke-3: 234 Angka ke-4: 986 Angka ke-5: 286 Angka ke-6: 277 Angka ke-7: 356 Angka ke-8: 989 Array setelah diurutkan: 111 234 277 286 356 456 986 989
Silahkan coba sebentar membuat kode program ini.
Tips Membuat Kode Program Mengurutkan Angka
Soal ini melatih pemahaman terkait array dan algoritma sorting. Berikut tutorial pendahuluan yang bisa diikuti:
Setiap angka yang akan diurutkan perlu di simpan ke dalam sebuah array. Array inilah yang akan kita proses menggunakan algoritma insertion sort.
# Pengertian Algoritma Insertion Sort
Insertion sort adalah algoritma pengurutan yang bekerja dengan cara menyisipkan element baru ke dalam posisi yang tepat dalam array yang sudah terurut. Algoritma ini dimulai dari element kedua, dan membandingkannya dengan element pertama. Jika element kedua lebih kecil dari element pertama, maka element kedua disisipkan di depan element pertama. Proses ini diulangi untuk element ketiga, keempat, dan seterusnya.
Algoritma Insertion Sort memiliki langkah-langkah sebagai berikut:
- Mulai dari element kedua dalam array.
- Bandingkan element kedua dengan element pertama.
- Jika element kedua lebih kecil dari element pertama, maka sisipkan element kedua di depan element pertama.
- Ulangi langkah 2 dan 3 untuk elemen-element berikutnya.
Pada langkah 2 dan 3, element kedua akan dibandingkan dengan elemen-element sebelumnya secara berturut-turut. Jika element kedua lebih kecil dari element sebelumnya, maka element kedua akan disisipkan di depan element tersebut.
Ilustrasi cara kerja algoritma insertion sort
Kelebihan algoritma insertion sort:
- Algoritma insertion sort relatif sederhana dan mudah dipahami.
- Algoritma insertion sort dapat digunakan untuk mengurutkan array dengan berbagai ukuran.
- Algoritma Insertion Sort efisien untuk mengurutkan array yang sudah terurut atau hampir terurut.
Kekurangan algoritma insertion sort:
- Algoritma insertion sort memiliki kompleksitas waktu O(n2), yang artinya waktu eksekusi algoritma akan meningkat secara kuadrat seiring dengan bertambahnya ukuran array.
Secara umum, algoritma insertion sort cocok digunakan untuk mengurutkan array kecil atau array yang tidak perlu diurut dengan cepat.
Kode Program C++ Mengurutkan Angka dengan Algoritma Insertion Sort
Berikut salah satu solusi dari soal mengurutkan angka array dengan algoritma insertion sort menggunakan bahasa pemrograman C++:
#include <iostream>
using namespace std;
int main() {
cout << "## Program C++ Mengurutkan Angka (Insertion Sort) ##" << endl;
cout << "=====================================================" << endl;
cout << endl;
int i, j, n, key;
// Baca angka input dari user
cout << "Input jumlah element array: ";
cin >> n;
cout << endl;
int arr[n];
cout << "Input "<< n << " angka (dipisah dengan enter): ";
cout << endl;
for(i = 0; i < n; i++){
cout << "Angka ke-" << i+1 <<": ";
cin >> arr[i];
}
// Urutkan array dengan algoritma insertion sort
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
// Tampilan hasil pengurutan
cout << endl;
cout << "Array setelah diurutkan: ";
for (i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Pada awal kode program di baris 9 terdapat deklarasi 4 variabel: i, j, n dan key dengan tipe data integer. Variabel i dan j nantinya akan kita pakai di dalam perulangan sebagai variabel counter, lalu variabel n dipakai untuk menyimpan jumlah angka. Untuk variabel key, dipakai ketika membuat algoritma insertion sort.
Lalu di baris 12-13 user diminta untuk menginput jumlah angka yang ingin diurutkan. Angka ini akan disimpan ke dalam variabel n.
Kode program lalu membuat array sejumlah n dengan perintah int arr[n] di baris 16. Perulangan for dipakai untuk membaca setiap data dan disimpan ke dalam variabel arr.
Algoritma insertion sort ada di baris 26-36. Algoritma ini bekerja dengan cara membandingkan element ke-i dengan element-element sebelumnya. Jika element ke-i lebih kecil dari element sebelumnya, maka element ke-i akan disisipkan di depan element tersebut.
Hasilnya, variabel arr akan berisi array yang sudah terurut, untuk selanjutnya ditampilkan dengan perulangan for di baris 41-43.
Kode Program C++ Algoritma Insertion Sort dengan Function
Sebagai bonus latihan, kita bisa membuat function terpisah untuk algoritma insertion sort. Berikut modifikasi dari kode program sebelumnya:
#include <iostream>
using namespace std;
// Buat function dengan algoritma insertion sort
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() {
cout << "## Program C++ Mengurutkan Angka (Insertion Sort) ##" << endl;
cout << "=====================================================" << endl;
cout << endl;
int i, n;
// Baca angka input dari user
cout << "Input jumlah element array: ";
cin >> n;
cout << endl;
int arr[n];
cout << "Input "<< n << " angka (dipisah dengan enter): ";
cout << endl;
for(i = 0; i < n; i++){
cout << "Angka ke-" << i+1 <<": ";
cin >> arr[i];
}
// Urutkan array dengan algoritma insertion sort
insertionSort(arr, n);
// Tampilan hasil pengurutan
cout << endl;
cout << "Array setelah diurutkan: ";
for (i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Sekarang di baris 5-17 terdapat pendefinisian function insertionSort(). Function ini memiliki 2 parameter arr[] dan n yang dipakai untuk menampung array asal dan jumlah element array yang akan diurutkan.
Kode yang diperlukan kurang lebih sama seperti versi sebelumnya.
Pemanggilan function ini dilakukan di baris 41 dengan perintah insertionSort(arr, n). Hasilnya, isi variabel arr akan langsung terurut.
Itulah bahasan kita tentang implementasi algoritma sorting insertion sort dalam bahasa pemrograman C++. Untuk lebih memahami cara kerjanya, silahkan ambil kertas lalu buat tabel dan tulis apa saja isi variabel arr, i, n dan key dalam setiap iterasi.
Untuk algoritma sorting lain seperti bubble sort dan selection sort akan kita bahas di tutorial terpisah. Semoga bisa bermanfaat.