Penjelasan lengkap insertion sort C++

Penjelasan lengkap insertion sort C++

Posted by Clevo

Monday, July 29, 2019

Algoritma CPP Pemrograman Sorting

Insertion sort adalah salah satu algoritma mengurutkan bilangan yang hampir sama dengan cara kita mengurutkan kartu saat bermain kartu di tangan kita. Insertion sort memiliki kompleksitas O(n²)  sama seperti algoritma pengurutan bubble sort dan selection sort.

Saat bermain kartu kita biasanya memindahkan kartu agar terurut dari yang paling lemah hingga paling kuat. Saat terdapat kartu yang lebih lemah kita menyisipkannya di bagian paling kiri, namun ketika terdapat kartu yang lebih kuat, kita menyisipkannya di bagian kanan. Dengan melakukannya sebanyak n kali, kita memperoleh kartu yang terurut sempurna.

Untuk anda yang masih bingung apa yang dilakukana dalam insertion sort baca deskripsi berikut ini:

1. Lihat kartu bagian kiri,
2. Bandingkan kartu dengan kartu sebelumnya bagian kiri,
3. Apabila sampai dengan kartu lebih keci, sisipkan kartu disebelah kiri kartu pembanding,
4. Ulangi sampai kartu terurut sempurna.

Best case dari insertion sort apabila kartu telah terurut sempurna. Pikirkan saat anda mendapat kartu yang sudah terurut, anda tidak perlu mengurutkan kembali bukan. Karena itu kartu yang sudah terurut adalah best case dari insertion sort.

Worst case dari insertion sort apabila kartu terurut terbalik. Kompleksitas dari sorting dengan kasus seperti ini akan mendekati n² . Jika kita bayangkan kartu ditangan dengan urutan terbalik, kita dengan mudah untuk mengurutkan dengan membalikkannya. Namun tidak dengan insertion sort. Akan terjadi banyak sekali pertuaran dengan kartu lainnya.

Menukar nilai dua variabel

Setelah mengerti bagaimana insertion sort bekerja, kita harus menukar letak array. Bagaimana cara melakukannya? Perhatikan potongan program dibawah ini!

temp = bil[i];

bil[i] = bil[0];

bil[0] = temp;

Misalkan i adalah index dengan nilai yang telah dibandingkan, temp adalah variabel yang digunakan untuk menyimpan sementara nilai dari bilangan paling kecil / minimum. Dengan menyimpan sementara variabel yang digunakan untuk menukar nilai kita dapat menukarkannya layaknya menukar wadah segelas kopi dengan segelas susu.

Dengan deskripsi dan cara menukar nilai diatas seharusnya. Silakan mencoba membuat insertion sort dari deskripsi diatas. Jika ada kesulitan berikut ini source code insertion sort bahasa C++.

Source code insertion sort C++

Berikut ini adalah kode program dari insertion sort.

#include <iostream>

using namespace std;

int main() {

int bil[] = {98, 21, 43, 34, 23, 65, 86, 21, 43, 1};

int n = sizeof bil / sizeof(int);

int temp;

int j;

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

temp = bil[i];

j = i - 1;

while(j >= 0 && bil[j] > temp){

bil[j+1] = bil[j];

j = j - 1;

}

bil[j+1] = temp;

}

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

cout << bil[i] << " ";

}

 Kode program diatas menggunakan while karena kita menginginkan berhenti disaat yang belum kita ketahui, dalam artian jika salah satu kondisi diatas program akan berhenti melakukan looping.

Insertion sort jarang digunakan karena kompleksitasnya yang n² . Program biasanya dibuat dari  sorting yang lebih cepat dengan kompleksitas yang lebih rendah. Algoritma sorting yang memiliki kompleksitas yang sama dengan insertion sort seperti bubble sort dan selection sort. Sementara itu algoritma sorting yang memiliki kompleksitas lebih rendah yakni O(n log n) ada algoritma merge sort, quick sort dan heap sort.

Baca juga : Penjelasan lengkap bubble sort

Baca juga : Penjelasan lengkap selection sort

Algoritma insertion sort akan melakukan n kali perbandingan jika bilangan sudah terurut. 

Ditulis Clevo Pada July 29, 2019 Komentar