Seçim Sıralaması Java Örnekli Program

Seçimli Sıralama nasıl çalışır?

Seçimli Sıralama aşağıdaki gibi basit bir sıralama algoritması uygular:

• Algoritma tekrar tekrar en düşük elemanı arar.
• Geçerli öğeyi en düşük değere sahip öğeyle değiştir
• Seçim sıralamasının her yinelemesinde/geçişinde öğeler değiştirilir.

Bu nedenle her geçiş, şu hususu ele alır: dizi Algoritma, iki bölge olarak ele alınır: soldan büyüyen sıralı bir blok ve sağdan küçülen sıralanmamış bir blok. Algoritma, sıralanmamış bloğu dolaşır, karşılaştığı en küçük değerin indeksini hatırlar ve bu değeri sıralanmamış ilk konumla değiştirir.

Her geçişte yalnızca bir değişim gerçekleştiği için, n elemanlı bir dizi en fazla n-1 değişimden sonra sıralanır. Bu özellik, bu rutini diğer başlangıç ​​seviyesi rutinlerden ayıran şeydir. Java Verileri çok daha sık hareket ettiren sıralama algoritmaları.

MKS tracAşağıda, bir sonraki bölümdeki programın çalışma zamanında yazdırdığı örnek dizi {860, 8, 200, 9} aynen verilmiştir.

Bu konuda iki detay var. tracÜzerinde durmaya değer noktalar var. Birincisi, 3. geçişte sıralama değişmese bile hala bir takas rapor ediliyor, çünkü kalan en küçük değer zaten mevcut dizinde bulunuyor ve program elemanı kendisiyle değiştiriyor. İkincisi, karşılaştırma sayısı her geçişte bir azalıyor (üç, sonra iki, sonra bir), bu da sayfanın aşağısındaki karmaşıklık rakamlarının ardındaki örüntüyü oluşturuyor.

Java Seçim Sıralamasını uygulayacak program

Aşağıdaki sınıf SelectionSortAlgo olarak adlandırılır ve com.guru99 paketinde yer alır. main() metodu örnek diziyi tanımlar, yazdırır, sıralama için selection() metoduna iletir ve tekrar yazdırır. printArray() yardımcı metodu tüm elemanları tek bir satıra yazar; bu da okunabilir adım adım log çıktısını oluşturur.

`selection()` fonksiyonunun içinde, dış döngü sıralı ve sıralı olmayan bölgeler arasındaki sınırı belirler, `index` değişkeni şimdiye kadar görülen en küçük değerin konumunu tutar ve her geçişin sonundaki üç atama işlemi takası gerçekleştirir.

package com.guru99;
 
public class SelectionSortAlgo {
 
	public static void main(String a[])
	{  
		int[] myArray = {860,8,200,9}; 
		
		System.out.println("------Before Selection Sort-----");
 
		printArray(myArray);
 
 
		selection(myArray);//sorting array using selection sort  
 
		System.out.println("-----After Selection Sort-----");  
 
		printArray(myArray); 
	} 
	
		public static void selection(int[] array)
	{  
		for (int i = 0; i < array.length - 1; i++)  
		{  System.out.println("Sort Pass Number "+(i+1));
			int index = i;  
			for (int j = i + 1; j < array.length; j++)
			{   
			    System.out.println("Comparing "+ array[index]  + " and " + array[j]);  
				if (array[j] < array[index]){ 
				System.out.println(array[index]  + " is greater than " + array[j] );
					index = j;
				
				
				}  
			}  
 
			int smallerNumber = array[index];   
			array[index] = array[i];  
			array[i] = smallerNumber;  
			System.out.println("Swapping Elements: New Array After Swap");
			printArray(array);
		}  
	}  
	static void printArray(int[] array){
	    
	    for(int i=0; i < array.length; i++)
		{  
			System.out.print(array[i] + " ");  
		} 
	    System.out.println();
	    
	}
 
}

Çıktı:

Sınıfın derlenmesi ve çalıştırılması, her geçişte bir çıktı bloğu içeren aşağıdaki konsol çıktısını üretir.

------Before Selection Sort-----
860 8 200 9 
Sort Pass Number 1
Comparing 860 and 8
860 is greater than 8
Comparing 8 and 200
Comparing 8 and 9
Swapping Elements: New Array After Swap
8 860 200 9 
Sort Pass Number 2
Comparing 860 and 200
860 is greater than 200
Comparing 200 and 9
200 is greater than 9
Swapping Elements: New Array After Swap
8 9 200 860 
Sort Pass Number 3
Comparing 200 and 860
Swapping Elements: New Array After Swap
8 9 200 860 
-----After Selection Sort-----
8 9 200 860

Bu örneği ilk kez çalıştıran acemiler iki sorunla karşılaşır. Çünkü dosya şunu belirtiyor: package com.guru99;Kaynak, eşleşen bir ortamda bulunmalıdır. com/guru99 Aksi takdirde derleyici paket veya sınıf adı uyuşmazlığı bildirir. Sınıf daha sonra tam nitelikli adıyla başlatılmalıdır. java com.guru99.SelectionSortAlgo, çünkü sade java SelectionSortAlgo NoClassDefFoundError hatası verir.

Döngü sınırları, sık karşılaşılan diğer bir tuzaktır. Dış döngü şu noktada durur: array.length - 1 ve iç döngü şuradan başlar: i + 1Sınırlardan herhangi birinin değiştirilmesi fazladan boş bir geçişe veya ArrayIndexOutOfBoundsException hatasına neden olur.

Seçme Sıralama Algoritmasının Zaman ve Alan Karmaşıklığı

Programdaki iç döngü her zaman dizinin sonuna kadar çalışır, bu nedenle algoritma verilerin nasıl göründüğüne bakılmaksızın aynı sayıda karşılaştırma yapar. n elemanlı bir dizi için bu toplam n(n-1)/2'dir; dört elemanlı örnek için bu altıya eşittir ve yukarıdaki çıktı gerçekten de tam olarak altı karşılaştırma satırı yazdırır.

Bu düzgün sıralanmış rakamlardan üç sonuç çıkarılabilir:

• Seçmeli sıralama uyarlanabilir değildir. Sıralanmış girdi, tersine çevrilmiş girdiyle tam olarak aynı maliyete sahiptir, bu nedenle erken çıkış kısayolu gibi bir şey söz konusu değildir. kabarcık sıralaması sunmaktadır.
• Algoritmanın en güçlü yanı takas sayısının düşük olmasıdır. En fazla n-1 takas gerçekleşir ki bu, diğer basit sıralama algoritmalarının yapabileceği karesel sayıdaki hareketten çok daha azdır.
• Bellek kullanımı sabittir. Sadece döngü sayaçları ve iki geçici değişken olan index ve smallerNumber gereklidir, bu nedenle yardımcı alan O(1)'dir ve sıralama yerinde gerçekleşir.

Karesel büyüme pratik sınırdır. Dizi boyutunun iki katına çıkarılması, karşılaştırma işini yaklaşık dört katına çıkarır; bu nedenle seçim sıralaması, O(n log n) algoritmalarının doğru seçim olduğu üretim veri kümelerinden ziyade, eğitim, küçük diziler ve gömülü kod için daha uygundur.

Seçmeli Sıralama Algoritmasının Avantajları ve Dezavantajları

Algoritmanın nerede faydalı, nerede zararlı olduğunu anlamak, ona ne zaman başvurmanın mantıklı olduğuna karar vermeyi kolaylaştırır.

Avantajlar

• Mantık kısa ve anlaşılır olduğundan, ilk sıralama alıştırmalarından biri olarak standart bir şekilde yer almaktadır. ekleme türü.
• Veriler yerinde sıralandığı için ikinci bir dizi tahsis edilmez ve bellek kullanımı girdi miktarıyla artmaz.
• Bu, diziye en fazla n-1 yazma işlemi gerçekleştirir; bu da yazma işlemlerinin yavaş olduğu veya ortamı aşındırdığı depolama alanlarında önemlidir.
• Çalışma süresi tamamen tahmin edilebilir, çünkü karşılaştırma sayısı yalnızca dizi uzunluğuna bağlıdır.

Dezavantajlar

• Her bir durum O(n²) karmaşıklığındadır, bu nedenle algoritma büyük veri kümeleri için ölçeklenebilir değildir.
• Sıralanmış bir diziyi algılayamaz ve bu nedenle asla erken bitmez.
• Yukarıda gösterilen klasik form kararsızdır, bu nedenle iki eşit değer ters sırada sonuçlanabilir.
• Bu algoritma, neredeyse sıralı verilerde eklemeli sıralama algoritmasına göre daha sık karşılaştırma yapar; eklemeli sıralama algoritması ise doğrusal zamana yaklaşır.

Özetle, dizi küçük olduğunda ve her yazma işlemi maliyetli olduğunda seçim sıralama algoritmasını tercih edin; veri kümesi büyük olduğunda veya zaten sıralanmaya yakın olduğunda ise bu algoritmadan kaçının.

Seçim Sıralaması vs BubbleSort ve Ekleme Sıralaması Karşılaştırması

Her üç algoritma da karesel, yerinde karşılaştırmalı sıralama algoritmalarıdır, ancak girişin şekli değiştiğinde farklı davranırlar.

Tablo, yaygın bir mülakat cevabını açıklamaktadır. Seçim sıralaması, değişim sayısı bakımından üstün gelir; kabarcık sıralaması, zaten sıralı olan girdiyi tanıma konusunda üstün gelir; ve ekleme sıralaması, gerçek veriler genellikle kısmen sıralı olduğundan, pratikte üçü arasında genellikle en hızlısıdır. Dizi birkaç düzine elemanı geçtikten sonra, hiçbiri birleştirme sıralaması veya hızlı sıralama ile rekabet edemez.

SSS