Insertion Sort Dengan Algoritma Divide And Conquer Oleh: Yudi Setiawan
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 Di...
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 : "); jlh_data = scan.nextInt();
int
// 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]+" "); } // else {
Untuk Data yang belum terpisah
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]+" "); } // else {
Untuk Data yang belum digabung
//
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"); } } }
Tentang Penulis
Yudi Setiawan Saat ini aktif sebagai Mahasiswa di salah satu Universitas di kota Medan dengan mengambil bidang Fakultas Teknik dan Ilmu Komputer. Sangat senang dengan bahasa pemrograman Java dan Android.
