Insertion Sort ~ Membuat Program Insertion Sort dengan C++ Beserta Prosesnya [Sorting] ~~ Halo sobat helmyntest, Jumpa lagi nih dengan gw yang lagi semangat boging huehehe.. setelah kemarin gw ngeshare lanjutan aplikasi penjualan barang kali ini gw mau share aplikasi sorting dengan c++. Lanngsung aja sob cekibrot.
Insertion sort adalah sebuah metode pengurutan data dengan menempatkan setiap elemen data pada pisisinya dengan cara melakukan perbandingan dengan data – data yang ada. Inde algoritma dari metode insertion sort ini dapat dianalogikan sama seperti mengurutkan kartu, dimana jika suatu kartu dipindah tempatkan menurut posisinya, maka kartu yang lain akan bergeser mundur atau maju sesuai kondisi pemindahanan kartu tersebut. Dalam pengurutan data, metode ini dipakai bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array diurutkan.
Penganalogian Insertion Sort dengan pengurutan kartu
Berikut menjelaskan bagaimana algoritma Insertion Sort bekerja dalam pengurutan kartu, Anggaplah kita ingi mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar.
- Dimulai dengan posisi tangan kosong, dan semua kartu berada diatas meja. Dan anggaplah kita akan menyusun kartu ke tangan kiri kita.
- Mengamil kartu pertama dari meja dan meletakannya ke tangan kiri.
- Mengambil kartu kedua dan membandingkannya dengan kartu yang sudah ada di tangan kiri.
- Jika kartu yang diambil dari meja memenuhi syarat perbandingan, maka kartu tersebut akan diletakan didepan kartu yang dibandingkan, serta kartu yang lain yang telah dibandingkan akan bergeser mundur (ke belakang).
Proses ini akan berlangsung sampai semua kartu akan terurutkan dengan benar sesuai criteria pengurutannya.
Demikian juga halnya dalam pengurutan data.
Jika data sudah ada, maka pengurutan dimulai dengan mengambil satu data dan membandingkannya dengan data-data yang ada didepannya. Jika data yang diambil memenuhi syarat perbandingan, maka data yang diambil tersebut akan diletakan di depan data yang dibandingkan, kemudian data-data yang dibandingkan akan bergeser mundur.
Catatan : Dalam hal pengurutan data dengan metode insertion sort ini, data yang diambil pertama adalah data kedua, kemudian data yang diambil akan dibandingkan dengan data – data yang ada disebelah kiri / data sebelumnya (data-data sebelum data yang diambil). Jika proses tersebut selesai, maka akan dilanjutkan dengan data-data selanjutnya (data ke-3, data ke-4… dan seterusnya). Proses akan berlangsung sampai data – data terurutkan dengan benar.
Berikut adalah simulasi Algoritma Insertion Sort
Jika digambarkan secara singkat, maka algoritma Insertion sort ini dapat digambar sebagai berikut.
 |
| Simulasi Insertion Sort |
Dari gambaran proses pengurutan/ sorting data di atas dapat diketahui bagaimana data-data tersebut berpindah posisi dari satu index ke index lain dalam satu array. Untuk detail proses pengurutan diatas, dapat disimak melalui detail simulasi berikut.
Data awal : 5, 2, 4, 6, 1, 3
Jumlah Index = 6 dimulai dari 0 s/d 5
Anggaplah index adalah ‘I’,
Untuk setiap proses pengurutan data, perbandingan data dimulai dari index kedua (dalam hal ini i=1)
Proses I:
i=1, x=1; j=0
x<j à2<5? — true =2, 5, 4, 6, 1, 3
Proses II
i=2, j=1, x=2
x<j à 4<5 — true = 2, 4, 5, 6, 1, 3 j=j-1, Jika benar x=x-1
x<j à4<2 — false = 2, 4, 5, 6, 1, 3
Proses III
I=3, j=2, x=3
x<j à6<5 — false = 2, 4, 5, 6, 1, 3 j=j-1 jika sebuah proses bernilai false, maka proses tersebut tidak akan dilanjutkan, karena secara otomatis data yang ada disebelah kiri semuanya sudah terurut dengan benar.
Proses IV
i=4, j=3, x=4
x<j à1<6 — true = 2, 4, 5, 1, 6, 3 j=j-1, jika benar maka x=x-1
x<j à 1<5 — true = 2, 4, 1, 5,6, 3 j=j-1 , jika benar maka x=x-1
x<j à1<4 — true = 2, 1, 4, 5,6, 3 j=j-1, jika benar maka x=x-1
x<j à 1<2 — true = 1, 2, 4, 5,6, 3
Proses V
i=5, j=4, x=5
x<j à3<6 — true = 1, 2, 4, 5,3, 6 j=j-1, jika benar maka x=x-1
x<j à3<5 — true = 1, 2, 4, 3, 5, 6 j=j-1, jika benar maka x=x-1
x<j à3<4 — true = 1, 2, 3, 4, 5, 6 j=j-1, jika benar maka x=x-1
x<jà3<2 — false = 1, 2, 3, 4, 5, 6 j=j-1
Berikut adalah penerapannya di dalam program
#include <stdio.h>
#define n 7
using namespace std;
int main(){
int A[n]={9, 5, 3, 13, 11, 1, 7};
int k, i, x;
printf("Sebelum disort\n");
for(i=0; i<=n-1; i++)
printf("%d ", A[i]);
printf("\n");
for (k=1; k<=n-1; k++){
x=A[k];
for (i=k-1; x<A[i] && i>=0; i--){
A[i+1]=A[i];
}
A[i+1]=x;
printf("\n ");
for (i=0; i<=n-1; i++)
printf("%d ", A[i]);
}
printf("\n\nSesudah Sort \n");
for (i=0; i<=n-1; i++)
printf("%d ", A[i]);
}
Berikut output programnya sob:
Oke sob sekian untuk postingan kali ini mengenai Insertion Sort ~ Membuat Program Insertion Sort dengan C++ Beserta Prosesnya [Sorting], semoga bermanfaat untuk sobat semua. Jika ada yang ingin ditanyakan silahkan berkomentar sob. Terimakasih sampai jumpa dipostingan gw berikutnya.