Eklemeli Sıralama Algoritması Java Program Örneği ile

Eklemeli Sıralama Algoritması Nedir?

Eklemeli sıralama, küçük veri kümeleri için uygun olan basit bir sıralama algoritmasıdır. Her yineleme sırasında algoritma:

• Bir diziden bir öğeyi kaldırır.
• Bunu, içindeki en büyük değerle karşılaştırır dizi.
• Öğeyi doğru konuma taşır.

Bu davranış, bir kart oyuncusunun elini düzenleme şeklini yansıtır: her yeni kart alınır ve doğru yere yerleşene kadar her büyük kartın yanından sola doğru itilir. Tüm kaydırmalar orijinal dizi içinde gerçekleştiği için, eklemeli sıralama hem yerinde hem de kararlıdır.

Bu da başlangıç ​​seviyesindeki kullanıcılar için uygun ürünler ailesine aittir. Java sıralama rutinleri olarak kabarcık sıralamasıAncak normalde zaten kısmen sıralı olan veriler üzerinde çok daha az yazma işlemi gerçekleştirir.

Eklemeli Sıralama Algoritması Süreci

Ekleme sıralama algoritması işlemi grafiksel olarak şu şekilde çalışır:

Animasyon aynı üç adımı tekrarlıyor. Java Aşağıdaki program çalışır. Deneme çalıştırma tablosu tracBu adımları, programın çalışma zamanında yazdırdığı şekilde, {860, 8, 200, 9} örnek dizisi üzerinde aynen uygulayın.

Dikkat edin, 3. aşamada iki karşılaştırma yapılması gerekiyor çünkü 9 numaralı anahtarın iki büyük değerin üzerinden geçmesi gerekiyor. Bu nedenle, her bir elemanın başlangıç ​​sırasının ne kadar bozuk olduğuna bağlı olarak karşılaştırma sayısı artar.

Java Eklemeli Sıralama Algoritmasını Kullanarak Bir Diziyi Sıralamak için Program Örneği:

Aşağıdaki program {860, 8, 200, 9} dizisini sıralar ve her karşılaştırma ve her kaydırmanın görünür olması için çalışan bir yorum yazdırır. Programı şu şekilde kaydedin: InsertionSortExample.java ve bunu herhangi bir JDK 8 veya daha yeni sürümüyle derleyin.

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();
	    
	}
}

Sınıfı çalıştırmak şu sonucu üretir: tracBurada gösterilen her biri. Sıralama Geçiş Numarası Her satır, dış döngünün bir yinelemesini işaretler ve her takas işleminden sonra yazdırılan satır, dizinin o anki durumunu gösterir.

Code Çıktı:

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

Eklemeli Sıralama Algoritmasının Zaman ve Alan Karmaşıklığı

Eklemeli sıralama algoritmasının performansı, girdinin zaten ne kadar sıralı olduğuna büyük ölçüde bağlıdır; bu nedenle en iyi durum ve en kötü durum, büyüme açısından tam bir mertebe farkı gösterir.

Alan kullanımı çok daha basit. Sadece sayaçlar. i, j, n hem de key Oluşturulur ve dizi yerinde yeniden düzenlenir, bu nedenle girdi ne kadar büyürse büyüsün yardımcı alan O(1) olur.

İç döngü daha küçük bir değere ulaştığı anda durduğu için, eklemeli sıralama uyarlanabilir olarak tanımlanır: giriş sıralı düzene ne kadar yakınsa, çalışma süresi de doğrusala o kadar yaklaşır.

Eklemeli Sıralamanın Avantajları ve Dezavantajları

Eklemeli sıralama algoritması, ortalama değerinin karesel olmasına rağmen, sabit faktörlerinin çok küçük olması ve davranışının tahmin edilebilir olması nedeniyle üretim kütüphanelerinde varlığını sürdürmektedir.

Avantajlar

• Yazması basit ve kullanımı kolay. tracElle yazılması, hem öğretim hem de mülakatlar için uygun olmasını sağlar.
• Kararlı bir yapı olduğundan, aynı anahtarı paylaşan kayıtlar orijinal göreceli sıralarını korur.
• Yerinde işlem, giriş dizisinin ötesinde yalnızca O(1) ek belleğe ihtiyaç duyar.
• Uyarlanabilir, zaten neredeyse sıralanmış verilerde O(n) karmaşıklığına ulaşır.
• Çevrimiçi olması, yeni öğeler gelmeye devam ederken bile bir listeyi sıralayabileceği anlamına gelir.

Dezavantajlar

• Rastgele veya ters sıralı girişlerde karesel zaman karmaşıklığı, onu büyük diziler için uygunsuz hale getirir.
• Her kaydırma işlemi diziye veri yazar, bu nedenle seçim sıralamasına göre daha fazla veri taşır.
• Giriş verisi birkaç düzine elemanı geçtikten sonra, birleştirme sıralaması ve hızlı sıralama onu rahatlıkla geride bırakır.

Pratik bir kural olarak, dizi küçük olduğunda, veriler neredeyse sıralı olduğunda veya böl ve yönet sıralaması bir bölümü birkaç elemana indirgediğinde eklemeli sıralama algoritmasına başvurulmalıdır.

Ekleme Sıralaması vs BubbleSort ve Seçim Sıralaması

Üç algoritmanın tamamı karesel karşılaştırmalı sıralama algoritmalarıdır, ancak kararlılıkları, sıralı girdilere verdikleri tepkiler ve gerçekleştirdikleri yazma sayısı bakımından farklılık gösterirler.

Yazma işlemi maliyetli olduğunda, en az takas işlemi gerçekleştirdiği için seçim sıralaması kazanır. Ekleme sıralaması ise bu ölçekte neredeyse her yerde, özellikle kısmen sıralı verilerde kazanır; bu nedenle, arkadaki gibi kütüphane sıralama algoritmaları tercih edilir. ortak Java egzersizleri ve JDK'nın iç yapısı çok küçük bölümler için buna geçiş yapıyor.

SSS