Algoritma Pemrograman Java Sorting : Insertion Sort

Apa Itu Sorting Dalam Java?

Dalam bahasa sehari-hari, kita mengenal sortir atau sorting. Sorting yaitu proses atau kegiatan untuk memilih atau menyusun sesuatu.  Bagi para  pemula dalam belajar Java, pengetahuan mengenai teknik sorting data tentunya menjadi hal yang fundamental.

Sorting

Dalam pemrograman, pengertian sorting adalah suatu proses atau rangkaian cara untuk menyusun kembali himpunan dari objek dengan menggunakan aturan tertentu yang sudah ditetapkan.

Misalkan anda memiliki data angka-angka yang berjumlah n buah. Maka berdasarkan pada data awal,  anda akan memperoleh suatu input, dengan pengertian :

Input : Urutan dari n angka (c1, c2, c3....cn)

Selanjutnya, anda menyusun angka-angka tersebut dari nilai terkecil sampai nilai terbesar, maka anda akan memperoleh suatu output, dengan pengertian :

Output : Permutasi (Pengurutan kembali) dari (c'1, c'2, c'3...cn) yang sudah tersusun sehingga memenuhi kondisi  c'1 <= c'2 <= c3 <=...<=cn.




Angka yang kita harapkan untuk disusun juga dikenal dengan istilah keys.

Walaupun secara konsep anda mensorting suatu urutan, namun input yang datang adalah dalam bentuk array dengan jumlah n element.

Kemudian, bagian yang terpenting yaitu cara anda melakukan sorting tersebut sehingga masalah terpecahkan disebut dengan algoritma. 

Algoritma memberikan solusi terhadap masalah

Memahami Insertion Sort

Insertion sort adalah jenis sorting selain dari Selection sort yang menggunakan algoritma yang efisien untuk menyortir elemen dengan jumlah data yang kecil. 

Cara kerja insertion sort adalah sama seperti ketika anda menyusun kartu dari nilai terkecil ke nilai terbesar, dengan awalnya tangan kita tidak memegang kartu apapun.

Kemudian kita mengambil kartu pertama secara random (angka kartu tidak terlihat), dan kita simpan di posisi bagian paling kiri. 

Setelah itu kita ambil lagi kartu kedua secara random, bila kartu kedua ini memiliki nilai lebih kecil di bandingkan dengan kartu pertama, maka kartu kedua akan bertukar posisi dengan kartu pertama.

Selanjutnya kita ambil kartu berikutnya secara random, kemudian proses penyusunan atau sortir dilakukan berulang seperti di atas, maka hasil akhirnya kita akan memiliki seri kartu yang berururut dari nilai terkecil sampai nilai terbesar.

Apakah keuntungan menggunakan insertion sort?

Keuntungan menggunakan insertion sort adalah :

• Dapat diimplementasikan dengan simpel.
• Sangat efisien untuk data berukuran kecil.
• Insertion sort dapat langsung menyortir list data ketika menerima input.
• Secara praktikal lebih efisien dibandingkan dengan selection dan bubble sort.

Insertion Sort Dan Loop

Selanjutnya adalah tahap yang terpenting, bagaimana loop dalam hal ini adalah for loop bekerja dalam menjelajahi array untuk melakukan insertion sort.

Contoh :

Anda memiliki array seperti berikut :

int [] array = {5, 1, 4, 6, 2, 3}

Di samping ini adalah ilustrasi bagaimana insertion sort bekerja, bila anda memiliki data berupa angka dari 1 sampai 6, yang tersusun secara acak.

Kemudian dengan insertion sort, anda mensorting angka-angka tersebut sehingga berurutan secara ascending :

Perulangan pertama dari algoritma ini akan mengambil elemen kedua dari array. Jika elemen kedua tersebut memiliki nilai yang lebih kecil dibandingkan dengan elemen pertama, maka elemen kedua akan ditukar dengan elemen pertama.

Selanjutnya, perulangan kedua akan melihat elemen ketiga dan kemudian akan memasukkan elemen ketiga tersebut kedalam posisi yang tepat berdasarkan nilai dua elemen tadi, yaitu elemen pertama dan kedua.

Sehingga pada perulangan ke-i pada algoritma ini, maka elemen i yang pertama dalam array original akan disortir. 

Insertion sort penyusunan angka 1 - 6

Maka untuk sorting array :

int [] array = {5, 1, 4, 6, 2, 3}

menggunakan insertion sort, loop dapat dijelaskan sebagai berikut :

for (int i = 1; i < array.length; i++) {
masukkan array[i] ke dalam sublist array[0..i-1] sehingga
array[0..i] disorting.
}

Untuk memasukkan array[i] kedalam array[0..i-1], simpan terlebih dahulu array[i] ke variabel sementara, misalkan variabel tersebut adalah temp.

Kemudian pindahkan array[i-1] ke array[i] jika array[i-1] > temp, selanjutnya pindahkan array [i-2] ke array[i-1] jika array[i-2] > temp, demikian seterusnya, sampai array[i-k] <= temp atau k > i (maka kita telah mensortir elemen pertama).

Tetapkan temp ke array[i-k+1].

Contoh :

public class DemoInsertionSort {
    
    /** Method untuk mensorting angka */
    public static void insertionSort(int[] array) {
        
        for (int i = 1; i < array.length; i++) {
            
            /** Masukkan array[i] kedalam sublist yang disortir pada
            array[0..i-1] sehingga array[0..i] disortir. */
            
            //simpan terlebih dahulu array[i] ke dalam 
            //variabel sementara temp
            int temp = array[i];
            int k;
            
            for (k = i - 1; k >= 0 && array[k] > temp; k--) {
                array[k + 1] = array[k];
                }
            
            // Tetapkan element yang disortir kedalam array[k + 1]
            array[k + 1] = temp;
            
            }
        }
    
    public static void main (String [] args){
        
        //array sebelum insertion sort
        int[] array = {0, -2, 3, 1, 4, -4, 8, -6};
        
        DemoInsertionSort.insertionSort(array);
        
        //for loop untuk menampilkan elemen array
        //setelah insertion sort dilakukan
        for (int i = 0; i < array.length; i++)
          {
          System.out.println("Elemen di index " + i 
                  + " sekarang adalah " + array[i]);
          }
    }
 }

Output:
Elemen di index 0 sekarang adalah -6 
Elemen di index 1 sekarang adalah -4 
Elemen di index 2 sekarang adalah -2 
Elemen di index 3 sekarang adalah 0 
Elemen di index 4 sekarang adalah 1 
Elemen di index 5 sekarang adalah 3 
Elemen di index 6 sekarang adalah 4 
Elemen di index 7 sekarang adalah 8