Metode Insertion Sort di Java Console Oleh: Yudi Setiawan
Pada tutorial sebelumnya, saya pernah jelaskan metode Bubble Sort dan Selection Sort. Nah, untuk tutorial kali ini saya akan membahas tentang Insertion Sort. “Metode Pengurutan kok banyak banget sih? Padahal dari segi logika untuk melakukan pengurutan kan gampang tinggal buat aja looping dari data ...
Pada tutorial sebelumnya, saya pernah jelaskan metode Bubble Sort dan Selection Sort. Nah, untuk tutorial kali ini saya akan membahas tentang Insertion Sort. “Metode Pengurutan kok banyak banget sih? Padahal dari segi logika untuk melakukan pengurutan kan gampang tinggal buat aja looping dari data pertama sampai data terakhir dan kemudian, di bloknya ada statement pengkondisian jika data lebih besar atau lebih kecil maka tukar.” Yap, dari segi logika memang gampang namun, dari segi algoritma itu berbeda. Seperti pada tutorial sebelumnya, Bubble Sort dan Selection Sort. Kedua metode itu memang sama – sama untuk sorting namun, kalau Anda lihat proses algoritmanya itu jelas berbeda antara Bubble Sort dan Selection Sort. “Memangnya seberapa penting sih algoritma itu?” Yah, jelas sangat penting dong. Proses Sorting itu tidak akan tampak perbedaannya jika data yang Anda sorting itu masih sedikit. Bagaimana kalau Anda sorting Data perusahaan yang jumlahnya itu bisa beribu – ribu banyaknya bahkan berjuta – juta. Apa mau si user menunggu waktu 1 jam lebih atau 1 harian penuh hanya untuk menunggu proses sorting selesai sementara di sisi lain dia bisa mendapatkan hal yang lebih bagus dari itu yakni cukup 10 menit data akan terurut dengan benar. Nah, di sinilah pentingnya dari proses Algoritma. Tujuannya sama – sama untuk mengurutkan namun, dari segi kecepatan algoritma jelas berbeda.
Insertion Sort merupakan metode pengurutan dimana langkah – langkah ialah membandingkan dari data kedua ke data pertama (Data-N <==> Data-N-1). Berbeda dengan Bubble Sort dimana, proses perbandingannya dimulai dari Data Pertama sampai Data Terakhir. Untuk lebih jelasnya langsung masuk ke contoh kasus.
Data : 12 9 3 20 30 1
Proses Insertion Sort (Ascending) Iterasi 1: 12 9 3 20 30 1 → (Bandingkan Data 9 dengan 12) 9 12 3 20 30 1 → (Tukar Data 9 dengan 12)
Iterasi 2: 9 12 3 20 30 1 → (Bandingkan Data 3 dengan 12) 9 3 12 20 30 1 → (Tukar 3 dengan 12. Bandingkan 3 dengan 9) 3 9 12 20 30 1 → (Tukar 3 dengan 9)
Iterasi 3: 3 9 12 20 30 1 → (Bandingkan 20 dengan 12) 3 9 12 20 30 1 → (Tidak ada pertukaran)
Iterasi 4: 3 9 12 20 30 1 → (Bandingkan 30 dengan 20) 3 9 12 20 30 1 → (Tidak ada pertukaran)
Iterasi 5: 3 9 12 20 30 1 → (Bandingkan 1 dengan 30) 3 9 12 20 1 30 → (Tukar 1 dengan 30. Bandingkan 1 dengan 20) 3 9 12 1 20 30 → (Tukar 1 dengan 20. Bandingkan 1 dengan 12) 3 9 1 12 20 30 → (Tukar 1 dengan 12. Bandingkan 1 dengan 9) 3 1 9 12 20 30 → (Tukar 1 dengan 9. Bandingkan 1 dengan 3) 1 3 9 12 20 30 → (Tukar 1 dengan 3)
Penjelasan Proses Insertion Sort (Ascending) - Dalam Insertion Sort jumlah iterasi ialah sebanyak jumlah data – 1. Untuk kasus diatas, Jumlah Data ialah 6 maka, jumlah iterasinya ialah 6 – 1 = 5. Dan jumlah iterasi tersebut harus terpenuhi walaupun Data sudah terurut. - Setiap Iterasi memiliki proses dan jumlah proses tersebut tidak bisa ditentuin karena, proses akan berhenti jika Data sudah terurut. Bisa Anda lihat pada iterasi ke-3 dan ke-4. Pada iterasi 3 dan 4 proses pengecekannya cuma sekali namun, karena Data yang di cek memang sudah terurut dengan benar maka, proses pengecekan berhenti dan lanjut ke iterasi berikutnya. - Untuk iterasi ke-1, Proses perbandingan dimulai dari Data ke-2 dengan Data ke-1 (9 <==> 12). Karena, 9 < 12 maka, 9 tukar posisi dengan 12. - Untuk iterasi ke-2, Proses perbandingan dimulai dari Data ke-3 dengan Data ke-2 (3 <==> 12). Karena, 3 < 12 maka,3 tukar dengan 12. Selanjutnya, bandingkan lagi 3 dengan 9 (3 <==> 9). Karena 3 < 9 maka, 3 tukar dengan 9. - Untuk iterasi ke-3, Proses perbandingan dimulai dari Data ke-4 dengan Data ke-3 (20 <==> 12). Karena, 20 > 12 maka, tidak ada pertukaran. Posisi tetap tidak ada perubahan. - Untuk iterasi ke-4, Proses perbandingan dimulai dari Data ke-5 dengan Data ke-4 (30 <==> 20). Karena, 30 > 20 maka, tidak ada pertukaran. Posisi tetap tidak ada perubahan. - Untuk iterasi ke-5, Proses perbandingan dimulai dari Data ke-6 dengan Data ke-5 (1 <==> 30). Karena, 1 < 30 maka, 1 tukar posisi dengan 30. Selanjutnya, bandingkan lagi 1 dengan 20 (1 <==> 20). Karena, 1 < 20 maka, 1 tukar posisi dengan 20. Selanjutnya, bandingkan lagi 1 dengan 12 (1 <==> 12). Karena, 1 < 12 maka, 1 tukar posisi dengan 12. Kemudian, bandingkan lagi antara 1 dengan 9 (1 <==> 9). Karena, 1 < 9 maka, 1 tukar posisi dengan 9. Berikutnya, bandingkan lagi 1 dengan 3 (1
<==> 3). Karena, 1 < 3 maka, 1 tukar posisi dengan 3.
Dan Data setelah di sort adalah seperti berikut.
Data : 1 3 9 12 20 30
Gimana mudahkan? Konsepnya hampir sama seperti Bubble Sort hanya saja di Insertion Sort proses dimulai dari Data kedua (Data-N+1) dan di cek satu per satu ke Data sebelumnya(Data-N-1). Selain itu, prosesnya juga berbeda antara Bubble Sort dan Insertion Sort. Kalau di Bubble Sort jumlah proses tiap iterasinya selalu dikurang 1 sementara di Insertion Sort jumlah prosesnya akan terus bertambah apabila Data tersebut masih bisa ditukar.
Berikut ialah source code Insertion Sort
import import import import
java.io.BufferedReader; java.io.InputStreamReader; java.io.IOException; java.util.Random;
/** * * @author Yudi Setiawan * * Insertion Sort. * */ public class InsertionSort { public static void main(String[] args) throws IOException { // Objek BufferedReader BufferedReader dataIn = new BufferedReader(new InputStreamReader(System.in)); // Input jumlah Data System.out.print("Masukkan jumlah Data : "); jlh_data = Integer.parseInt(dataIn.readLine()); // Array Data untuk menampung nilai Data int[] data = new int[jlh_data]; // Menu Pengisian data System.out.println("\nMenu Pengisian Data");
int
System.out.println("1. Di input oleh user"); System.out.println("2. Di isi oleh program"); System.out.print("Pilihan : "); isi_data = Integer.parseInt(dataIn.readLine()); switch(isi_data) { case 1
:
//
int
Pengisian Data
oleh si User System.out.println(); for(int a = 0; a < jlh_data; a++) { System.out.print("Data ke-"+(a+1)+" : "); Integer.parseInt(dataIn.readLine());
data[a] = } break;
case 2 oleh program --> di isi secara acak
:
//
Pengisian Data
System.out.println(); for(int a = 0; a < jlh_data; a++) data[a] = new Random().nextInt(201); //
Tampilkan Data
yang di isi oleh program System.out.print("Data : "); for(int a = 0; a < jlh_data; a++) System.out.print(data[a]+" "); break; default : System.out.println("\nPilihan tidak tersedia"); } // Proses Insertion Sort System.out.println("\nProses Insertion Sort"); for(int a = 0; a < jlh_data-1; a++) { System.out.println("Iterasi "+(a+1)); for(int b = 0; b < jlh_data; b++) System.out.print(data[b]+"\t");
System.out.print("
--> Bandingkan "+data[a+1]+"
dengan "+data[a]); for(int b = a+1; b > 0; b--) { String pesan = " --> Tidak ada pertukaran"; if(data[b] < data[b-1]) { pesan = " --> "+data[b]+" tukar posisi dengan "+data[b-1]; // Proses Pertukaran int temp = data[b]; data[b] = data[b-1]; data[b-1] = temp; System.out.println(); for(int c = 0; c < jlh_data; c++) System.out.print(data[c]+"\t"); System.out.print(pesan); } else { System.out.println(); for(int c = 0; c < jlh_data; c++) System.out.print(data[c]+"\t"); System.out.print(pesan); break; } } System.out.println("\n"); } // Tampilkan hasil Sorting System.out.print("\nData setelah di Sorting : "); for(int a = 0; a < jlh_data; a++) System.out.print(data[a]+" "); } }
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.
