Algoritma Sortir Penyisipan di Java dengan Contoh Program

Apa itu Algoritma Insertion Sort?

Pengurutan penyisipan adalah algoritma pengurutan sederhana yang cocok untuk kumpulan data kecil. Selama setiap iterasi, algoritma:

• Menghapus elemen dari array.
• Membandingkannya dengan nilai terbesar di susunan.
• Memindahkan elemen ke lokasi yang benar.

Perilaku algoritma ini mencerminkan cara pemain kartu mengatur kartu di tangannya: setiap kartu baru diambil dan digeser ke kiri melewati setiap kartu yang lebih besar hingga berada di tempat yang tepat. Karena semua pergeseran terjadi di dalam susunan asli, pengurutan penyisipan (insertion sort) bersifat in-place dan stabil.

Ini termasuk dalam keluarga yang sama dengan perangkat lunak ramah pemula. Java rutinitas pengurutan sebagai semacam gelembungNamun, biasanya ia melakukan jauh lebih sedikit penulisan pada data yang sudah sebagian terurut.

Proses Algoritma Pengurutan Penyisipan

Berikut adalah cara kerja proses algoritma Insertion sort secara grafis:

Animasi tersebut mengulangi tiga langkah yang sama. Java Program di bawah ini dijalankan. Tabel uji coba tracLakukan langkah-langkah tersebut pada array sampel {860, 8, 200, 9}, persis seperti yang dicetak program saat dijalankan.

Perhatikan bahwa langkah ke-3 membutuhkan dua perbandingan karena kunci 9 harus melewati dua nilai yang lebih besar. Oleh karena itu, jumlah perbandingan bertambah seiring dengan seberapa jauh setiap elemen dimulai dari urutan yang salah.

Java Contoh Program Mengurutkan Array Menggunakan Algoritma Insertion Sort:

Program di bawah ini mengurutkan array {860, 8, 200, 9} dan mencetak komentar yang berjalan, sehingga setiap perbandingan dan setiap pergeseran terlihat. Simpan sebagai InsertionSortExample.java dan mengkompilasinya dengan JDK 8 atau versi yang lebih baru.

package com.guru99;
 
public class InsertionSortExample {
 
	
    public static void main(String a[])
    {    
        int[] myArray  = {860,8,200,9};  
        
        System.out.println("Before Insertion Sort");  
        
        printArray(myArray);
            
        insertionSort(myArray);//sorting array using insertion sort    
           
        System.out.println("After Insertion Sort");  
        
        printArray(myArray);   
    }    
 public static void insertionSort(int arr[]) 
	{  
        int n = arr.length;  
        
        for (int i = 1; i < n; i++)
        {   System.out.println("Sort Pass Number "+(i));
            int key = arr[i];  
            int j = i-1;  
            
            while ( (j > -1) && ( arr [j] > key ) ) 
            {  
            System.out.println("Comparing "+ key  + " and " + arr [j]); 
                arr [j+1] = arr [j];  
                j--;  
            }  
            arr[j+1] = key; 
            System.out.println("Swapping Elements: New Array After Swap");
            printArray(arr);
        }  
    }
 static void printArray(int[] array){
	    
	    for(int i=0; i < array.length; i++)
		{  
			System.out.print(array[i] + " ");  
		} 
	    System.out.println();
	    
	}
}

Menjalankan kelas tersebut menghasilkan trace ditunjukkan di sini. Masing-masing Urutkan Nomor Lulus Baris tersebut menandai satu iterasi dari loop luar, dan baris yang dicetak setelah setiap pertukaran menunjukkan array sebagaimana adanya pada saat itu.

Code Keluaran:

Before Insertion Sort
860 8 200 9 
Sort Pass Number 1
Comparing 8 and 860
Swapping Elements: New Array After Swap
8 860 200 9 
Sort Pass Number 2
Comparing 200 and 860
Swapping Elements: New Array After Swap
8 200 860 9 
Sort Pass Number 3
Comparing 9 and 860
Comparing 9 and 200
Swapping Elements: New Array After Swap
8 9 200 860 
After Insertion Sort
8 9 200 860

Kompleksitas Waktu dan Ruang dari Pengurutan Penyisipan (Insertion Sort)

Performa insertion sort sangat bergantung pada seberapa teratur input yang sudah ada, itulah sebabnya kasus terbaik dan kasus terburuk berbeda hingga satu orde pertumbuhan penuh.

Penggunaan ruang jauh lebih sederhana. Hanya konternya saja. i, j, n ke key dibuat, dan array diatur ulang di tempatnya, sehingga ruang tambahan adalah O(1) tidak peduli seberapa besar inputnya.

Karena loop bagian dalam berhenti segera setelah menemukan nilai yang lebih kecil, pengurutan penyisipan (insertion sort) digambarkan sebagai adaptif: semakin dekat input ke urutan terurut, semakin dekat waktu eksekusi ke arah linier.

Keuntungan dan Kerugian dari Insertion Sort

Algoritma insertion sort tetap digunakan dalam pustaka produksi meskipun memiliki rata-rata kuadratik, karena faktor konstannya sangat kecil dan perilakunya dapat diprediksi.

Kelebihan

• Mudah ditulis dan mudah digunakan. tracdengan tangan, yang membuatnya cocok untuk pengajaran dan wawancara.
• Stabil, sehingga catatan yang memiliki kunci yang sama mempertahankan urutan relatif aslinya.
• Dilakukan di tempat, hanya membutuhkan memori tambahan O(1) di luar array input.
• Adaptif, mencapai O(n) pada data yang sudah hampir terurut.
• Secara online, artinya sistem dapat mengurutkan daftar meskipun elemen baru masih terus berdatangan.

Kekurangan

• Waktu kuadratik pada input acak atau berurutan terbalik membuatnya tidak cocok untuk array besar.
• Setiap pergeseran menulis ke dalam array, sehingga memindahkan lebih banyak data daripada yang dilakukan oleh selection sort.
• Merge sort dan quicksort mengunggulinya dengan mudah begitu inputnya melebihi beberapa lusin elemen.

Aturan praktisnya adalah menggunakan insertion sort ketika array berukuran kecil, ketika data hampir terurut, atau ketika algoritma divide-and-conquer sort telah mengurangi partisi menjadi beberapa elemen saja.

Pengurutan Sisipan vs Bubble Sort vs Selection Sort

Ketiga algoritma tersebut merupakan pengurutan perbandingan kuadratik, namun berbeda dalam hal stabilitas, cara bereaksi terhadap input yang terurut, dan jumlah operasi penulisan yang dilakukan.

Selection sort unggul ketika operasi penulisan mahal, karena melakukan pertukaran paling sedikit. Insertion sort unggul hampir di semua tempat lain pada skala ini, terutama pada data yang sebagian terurut, itulah sebabnya algoritma pengurutan seperti yang ada di bawah ini digunakan. umum Java Latihan dan internal JDK beralih ke metode tersebut untuk partisi yang sangat kecil.

Pertanyaan Umum Demo Slot