Java : Insertion Sort Dengan Algoritma Divide And Conquer

Pada tutorial sebelumnya, saya pernah ada membahas tentang Insertion Sort. Nah, perbedaan antara Insertion Sort yang biasa dengan yang ini ialah di bagian Algoritmanya. Dimana, pada metode ini pengurutan dilakukan dengan cara Insertion Sort dan ditambah dengan metode Divide and Conquer. “Apa sih Divide and Conquer?” Divide and Conquer ialah algoritma yang mana pada Data yang ada akan dibagi menjadi beberapa SubData. Algoritma ini hampir mirip dengan Sorting Merge Sort yang membagi Data menjadi beberapa SubData namun, perbedaannya terletak pada saat proses Combine. Berikut sampel kasusnya.

Data :    5              9              2              1              3

Penyelesaian :

1. Tampilkan Data Sebelum di sorting.
2. Kemudian, Kita akan membagi Data tersebut secara satu per satu dimulai dari Data pertama sampai Data terakhir. Catatan : Kolom berwarna hijau berarti, Datanya masih bergabung. Sedangkan kolom berwarna merah, berarti sudah terpisah menjadi SubData.
   
   
3. Terlihat dari gambar diatas, semua Data telah terpisah menjadi beberapa SubData.
4. Langkah berikutnya, ialah menggabungkan kembali beberapa SubData yang telah terpisah menjadi satu Data yang utuh seperti semula dengan cara digabungkan per tahap sesuai dari iterasi 2 ke iterasi terakhir sembari di Sorting dengan metode Insertion Sort. Berikut gambarannya.
   
   
   
5. Baiklah akan saya jelaskan bagaimana proses Penggabungan pada gambar diatas.

Penjelasan :

• Pada iterasi 2, Gabungkan SubData 5 dengan 9 sembari di sorting. Karena 9 > 5 maka, tidak terjadi pertukaran. Perbandingan dilakukan dari SubData paling belakang sampai SubData Pertama.
• Pada iterasi 3, Gabungkan SubData 5, 9 dan 2 sembari di sorting. Perbandingan dilakukan dari Data yang paling belakang. 2 bandingkan dengan 9. Karena, 2 < 9 maka, SubData 2 bertukar tempat dengan SubData 9. Kemudian, bandingkan lagi 2 dengan 5. Karena 2 < 5 maka, SubData 2 bertukar tempat dengan SubData 5.
• Pada Iterasi 4, Gabungkan SubData 2, 5, 9 dan 1 sembari di sorting. Bandingkan SubData 1 dengan SubData 9. Karena 1 < 9 maka, SubData 1 bertukar tempat dengan SubData 9. Lanjut lagi bandingkan SubData 1 dengan SubData 5. Karena, 1 < 5 maka SubData 1 bertukar tempat dengan SubData 5. Bandingkan lagi SubData 1 dengan SubData 2. Karena 1 < 2 maka, SubData 1 bertukar tempat dengan SubData 2.
• Pada iterasi 5, Gabungkan SubData 1, 2, 5, 9 dan 3 sembari di sorting. Bandingkan SubData 3 dengan SubData 9. Karena 3 < 9 maka, SubData 3 bertukar tempat dengan SubData 9. Bandingkan lagi SubData 3 dengan SubData 5. Karena 3 < 5 maka, SubData 3 bertukar tempat dengan SubData 5. Bandingkan lagi SubData 3 dengan SubData 2. Karena 3 > 2 maka, tidak terjadi pertukaran. Dan hentikan proses perbandingan.

Maka, Data setelah di sorting dengan Insertion Sort menggunakan algoritma Divide and Conquer ialah menjadi sebagai berikut:

Data setelah di Sorting : 1             2              3              5              9

Berikut source code lengkapnya.

import java.util.Arrays;
import java.util.Scanner;

/**
 * 
 * @author Yudi Setiawan
 * 
 * Insertion Sort dengan algoritma Divide and Conquer
 *
 */

public class InsertionSortDAC
{
 public static void main(String[] args)
 {
  // Objek Scanner
  Scanner scan = new Scanner(System.in);
  
  // Input banyaknya Data
  System.out.print("Input banyaknya Data : "); int jlh_data = scan.nextInt();
  
  // Input nilai tiap Data
  int[] data = new int[jlh_data];
  for(int a = 0; a < jlh_data; a++)
  {
   System.out.print("Nilai Data ke-"+(a+1)+" : "); data[a] = scan.nextInt();
  }
  
  // Tampilkan Data
  System.out.println("Data Sebelum di Sorting : "+Arrays.toString(data));
  
  // Proses Algoritma Divide and Conquer
  // Divide (Pemisahan Data)
  System.out.println("\nDivide");
  for(int a = 0; a < data.length; a++)
  {
   System.out.println("Iterasi ke-"+(a+1));
   for(int b = 0; b < data.length; b++)
   {
    // Tanda pemisah di awal untuk memisah setiap Data dengan tanda | untuk Data yang sudah terpisah
    if(b == 0 || b <= a)
    {
     System.out.print("| "+data[b]+" ");
    }
    
    // Untuk Data yang belum terpisah
    else
    {
     System.out.print(" "+data[b]);
    }
    
    // Tanpa pemisah di akhir 
    if(b == a)
    {
     System.out.print("|");
    }
   }
   System.out.println("\n");
  }
  
  
  
  // Conquer atau Combine atau Merge (Penggabungan Data sembari di Sorting)
  System.out.println("Merge/Combine/Conquer");
  for(int a = 0; a < data.length-1; a++)
  {
   System.out.println("Iterasi ke-"+(a+2));
   // Proses Sorting Insertion Sort
   for(int b = a+1; b > 0; b--)
   {
    if(data[b] < data[b-1])
    {
     int temp = data[b];
     data[b] = data[b-1];
     data[b-1] = temp;
    }
   }
   
   for(int c = 0; c < data.length; c++)
   {
    // Untuk Data yang akan digabung
    if(c <= a+1)
    {
     System.out.print(data[c]+" ");
    }
    
    // Untuk Data yang belum digabung
    else
    { 
     // Pengecualian untuk Data iterasi terakhir
     if(a == data.length-1)
     {
      System.out.print(data[c]);
       continue;
     }
     
     System.out.print("| "+data[c]+" ");
     
     // Pmebatas untuk Data terakhir yang belum digabung
     if(c == data.length-1)
      System.out.print("|");
    }
    
    
    
    
   }
   System.out.println("\n");
  }
 }
}