Contoh program Algoritma insertion sort C++ – Insertion sort adalah sebuah algoritma pengurutan yang membandingkan dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan.
Karena algoritma insertion c++ ini bekerja dengan membandingkan elemen-elemen data yang akan diurutkan, algoritma ini termasuk juga dalam comparison-based sort.
Ide dasar dari algoritma Insertion Sort C++ ini adalah mencari tempat yang “tepat” untuk setiap elemen array, dengan cara sequential search. Lalu menyisipkan sebuah elemen array yang diproses ke tempatnya seharusnya. Proses ini dilakukan sebanyak N-1 tahapan (dalam sorting disebut sebagai “pass”), indeks dimulai dari 0.
Proses pengurutan dengan menggunakan algoritma Insertion Sort C++ dilakukan dengan cara membandingkan data ke-i (dimana i dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Bila ditemukan data yang lebih kecil maka akan disisipkan ke depan sesuai dengan posisi seharusnya.
Algoritma Insertion C++
Insertion sort ( metode penyisipan ) bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai seluruh array berhasil diurutkan. Juga metode ini mengurutkan bilangan bilangan yang telah dibaca, dan berikutnya secara berulang akan menyisipkan bilangan-bilangan dalam array yang belum terbaca ke sisi kiri array yang sudah terurut.
4 |
3 |
5 |
9 |
8 |
7 |
12 |
13 |
16 |
20 |
Kita perlu menyisipkan bilangan kedua elemen satu yaitu (3) ke dalam bagian depan sehingga yang paling depan adalah bagian yang terkecil.
3 |
4 |
5 |
9 |
8 |
7 |
12 |
13 |
16 |
20 |
Kemudian cek apa bilangan yang ketiga atau elemen ke empat yaitu (5) lebih kecil dari yang ke dua atau elemen ke tiga (4) atau yg pertama elemen nol (3) jika tidak, tidak akan melakukan penukaran. Dan akan menjadi seperti ini
3 |
4 |
5 |
9 |
8 |
7 |
12 |
13 |
16 |
20 |
Sekarang tiga bilangan pertama sudah terurutkan secara lelatip dan kita sisipkan bilangan selanjutnya kepada bilangan yg sudah terurut di depan nya setelah penyisipan.
Ulangi proses tersebut hingga bilangan terakhir disisipkan seperti ini :
Contoh Program Insertion Sort C++
#include <conio.h>
#include <iomanip>
using namespace std;
main(){
system (“color a”);
cout<<“===================================================================”<<endl;
cout<<“nttHARDIFAL”<<endl;
cout<<“= JURUSANt : TEKNIK INFORMATIKA”<<endl; cout<<“n===================================================================”<<endl;
int nilai [20];
int i,j,k,N;
int temp;
bool tukar;
cout<<“Masukan Banyak Bilangan :”;
cin>>N;
for (i=0; i<N; i++){
cout <<“Elemen Ke :” <<i<<” : “;
cin>>nilai [i];
}
cout <<“nData sebelumnya Diurut :”;
for (i=0;i<N;i++)
cout <<setw (3)<<nilai [i];
i=0;
tukar = true;
while ((i<=N-2) && (tukar)){
tukar = false;
for (j=N-1; j>=i+1; j–){
if (nilai [j] < nilai [j-1]){
temp =nilai [j];
nilai [j] = nilai [j-1];
nilai [j-1] = temp ;
tukar = true;
cout <<endl;
for (k=0; k<N; k++)
cout <<setw (3)<< nilai [k];
}
}i++;
}
cout <<“nData Setelah Diurutkan :”;
for (i=0; i<N; i++)
cout <<setw (3)<<nilai [i];
getch ();
}
Output Program Algoritma Insertion Sort C++:
