Pengurutan Sisip (Insertion Sort) pada Bahasa C

Metode pengurutan sisip merupakan sebuah metode  pengurutan membagi data menjadi 2 jadi bagian. Bagian pertama adalah bagian yang terurut dan bagian kedua adalah bagian yang belum terurut. Kemudian bagian yang belum terurut ditempat pada bagian yang terurut satu persatu sampai semua bagian yang belum terurut menjadi terurut.  Misalkan memiliki data 61 78 12 46 10 89 maka langkah pengurutannya adalah sebagai berikut :

  1. | 61 78 12 46 10 89
    • Pada data ini bagian yang terurut yang terletak di sebelah kiri tanda “|” belum memiliki data. Bagian yang belum terurut yang terletak di sebelah kanan tanda “|”, terdiri dari  61 78 12 46 10 89. Langkah selanjutnya adalah menggeser tanda “|”  geser sebanyak 1 data ke kanan.
  2. 61 | 78 12 46 10 89
    • Pada data ini bagian yang terurut yang terletak di sebelah kiri tanda “|”, yaitu 61. Bagian yang belum terurut yang terletak di sebelah kanan tanda “|”, terdiri dari  78 12 46 10 89.
    • Kemudian bandingkan 78 dengan data pada bagian yang terurut, karena pada bagian terurut tidak ada data yang lebih besar dari 78 maka tanda “|” geser sebanyak 1 data ke kanan.
  3. 61 78 | 12 46 10 89
    • Pada data ini bagian yang terurut yang terletak di sebelah kiri tanda “|”, yaitu 61 dan 78. Bagian yang belum terurut yang terletak di sebelah kanan tanda “|”, terdiri dari  12 46 10 89.
    • Kemudian bandingkan 12 dengan data pada bagian yang terurut. Perbandingan pertama dengan 78, karena 78 lebih besar dari 12 maka 78 menempati posisi 12, sehingga  data akan seperti berikut ini 61 12 78 | 46 10 89
    • Proses berlanjut dengan membandingkan 12 dengan 61, karena 61 lebih besar dari 12 maka 61 menempati posisi 12, sehingga  data akan seperti berikut ini 12 61 78 | 46 10 89.
  4. 12 61 78 | 46 10 89
    • Pada data ini bagian yang terurut yang terletak di sebelah kiri tanda “|”, yaitu 12, 61 dan 78. Bagian yang belum terurut yang terletak di sebelah kanan tanda “|”, terdiri dari  46 10 89.
    • Kemudian bandingkan 46 dengan data pada bagian yang terurut. Perbandingan pertama dengan 78, karena 78 lebih besar dari 46 maka 78 menempati posisi 46, sehingga  data akan seperti berikut ini 12 61 46 78 | 10 89
    • Proses berlanjut dengan membandingkan 46 dengan 61, karena 61 lebih besar dari 46 maka 61 menempati posisi 46, sehingga  data akan seperti berikut ini 12 46 61 78 | 10 89.
    • Proses berlanjut dengan membandingkan 46 dengan 12, karena 12 lebih kecil dari 46 maka tidak terjadi pergesaran, sehingga  data akan seperti berikut ini 12 46 61 78 | 10 89.
  5. Proses berulang sampai semua data terurut.

Pseudo Code Insertion Sort

Berikut merupakan pseduo code dari metode pengurutan Insertion Sort.

for i = 1 to n-1
    data_sisip = tabInt[i];
    j = i;
    while(j>0 and (tabInt[j-1]>data_sisip))do
        tabInt[j] = tabInt[j-1];
        j = j - 1;
    end while
    tabInt[j] = data_sisip;
end for

Terurut Menaik atau Terurut Menurun

Terurut Menaik artinya data terurut dari kecil ke besar maka pseudo kode .

while(j>0 and (data_sisip < tabInt[j-1]))do

Terurut Menaik artinya data terurut dari besar ke kecil maka pseudo kode .

while(j>0 and (data_sisip > tabInt[j-1]))do

Contoh kode lengkap pengurutan data dari  kecil ke besar dengan metode Insertion Sort sebagai berikut :

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#include <time.h> 
 
main(){ 
 
    int tabInt[1000]; 
    int i,j,data_sisip,random,n; 
    n=1000; 
 
    //masukan data random 
    srand(time(0)); 
    for(i=0;i<n;i++){ 
        random = rand() % n + 1; 
        tabInt[i]=random; 
    } 
 
    //keluarkan data 
    printf("Data Randomn"); 
    for(i=0;i<n;i++){ 
        printf("%d  ", tabInt[i]); 
    } 
    printf("nnData Sedang Diurutkannn"); 
 
    //proses mengurutkan dari kecil ke besar 
    for(i=1; i<n; i++){ 
        data_sisip = tabInt[i]; 
        j = i; 
        while((j>0) && (tabInt[j-1] > data_sisip)){            
            tabInt[j] = tabInt[j-1]; 
            j = j - 1; 
        }        
        tabInt[j] = data_sisip; 
    } 
 
    //keluarkan data 
    printf("nData dari kecil ke besarn"); 
    for(i=0;i<n;i++){ 
        printf("%d  ", tabInt[i]); 
   } 
}

Silahkan eksplorasi lebih lanjut ke Pengurutan Seleksi (Selection Sort) pada Bahasa C

Block AdBlock - Powered by Admiral