Algoritma Pemrograman Java Sorting : Insertion Sort

Apa Itu Sorting Dalam Java?

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

Sorting

Dalam pemrograman, pengertian sorting yaitu suatu proses atau rangkaian cara untuk menyusun kembali himpunan dari objek dengan memakai hukum tertentu yang sudah ditetapkan.

Misalkan anda mempunyai data angka-angka yang berjumlah n buah. Maka menurut 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 hingga 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 tiba yaitu dalam bentuk array dengan jumlah n element.

Kemudian, bab yang terpenting yaitu cara anda melaksanakan sorting tersebut sehingga problem terpecahkan disebut dengan algoritma. 

Algoritma memperlihatkan solusi terhadap masalah

Memahami Insertion Sort

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

Cara kerja insertion sort yaitu sama ibarat saat 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 bab paling kiri. 

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

Selanjutnya kita ambil kartu berikutnya secara random, lalu proses penyusunan atau sortir dilakukan berulang ibarat di atas, maka hasil jadinya kita akan mempunyai seri kartu yang berururut dari nilai terkecil hingga nilai terbesar.

Apakah laba memakai insertion sort?

Keuntungan memakai insertion sort yaitu :

• Dapat diimplementasikan dengan simpel.
• Sangat efisien untuk data berukuran kecil.
• Insertion sort sanggup pribadi menyortir list data saat mendapatkan input.
• Secara praktikal lebih efisien dibandingkan dengan selection dan bubble sort.

Insertion Sort Dan Loop

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

Contoh :

Anda mempunyai array ibarat berikut :

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

Di samping ini yaitu ilustrasi bagaimana insertion sort bekerja, bila anda mempunyai data berupa angka dari 1 hingga 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 mempunyai nilai yang lebih kecil dibandingkan dengan elemen pertama, maka elemen kedua akan ditukar dengan elemen pertama.

Selanjutnya, perulangan kedua akan melihat elemen ketiga dan lalu akan memasukkan elemen ketiga tersebut kedalam posisi yang sempurna menurut 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}

memakai insertion sort, loop sanggup 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 yaitu temp.

Kemudian pindahkan array[i-1] ke array[i] jikalau array[i-1] > temp, selanjutnya pindahkan array [i-2] ke array[i-1] jikalau 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                    + " kini yaitu " + array[i]);           }     }  } 

Output:
Elemen di index 0 kini yaitu -6 
Elemen di index 1 kini yaitu -4 
Elemen di index 2 kini yaitu -2 
Elemen di index 3 kini yaitu 0 
Elemen di index 4 kini yaitu 1 
Elemen di index 5 kini yaitu 3 
Elemen di index 6 kini yaitu 4 
Elemen di index 7 kini yaitu 8

Bagikan Artikel ini