Pengurutan Sisip (Insertion Sort) pada Bahasa Java

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 :

public class insertionSort {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] tabInt = {51,23,17,32,43,88};
        int i,j,data_sisip;
        
        for(i=1; i<6; 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; 
        } 
        for(i=0; i<6; i++){ 
            System.out.print(tabInt[i]+" ");
        }
    }
}

Berikut ini kode program pengurutan data random dengan metode Insertion Sort disertai waktu perhitungan lamanya proses pengurutan.

import java.util.Date;
public class InsertionSortRandom {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] tabInt = new int[100];
        int i,j,data_sisip,n,random;
        Date date1,date2;
        n=100;
        
        //isi data random
        for(i=0; i<n; i++){ 
            random = (int)(Math.random()*n);
            tabInt[i]=random;
        }
        
        //tampilkan data random
        System.out.println("Data Random");
        for(i=0; i<n; i++){ 
            System.out.print(tabInt[i]+" ");
        }
        
        date1 = new Date();
        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; 
        }
        date2 = new Date();        
        
        //tampilkan data terurut
        System.out.println("\nData Terurut");
        for(i=0; i<n; i++){ 
            System.out.print(tabInt[i]+" ");
        }
        
        //tampilkan waktu pengurutan
        System.out.println("\nWaktu Pengurutan :");
        System.out.println(date2.getTime() - date1.getTime()+" ms");
        
    }
}

Demikian penjelasan mengenai algoritma Insertion Sort, silahkan eksplorasi lebih lanjut