Výběr Třídění v Java Program s příkladem

Jak funguje výběrové řazení?

Selection Sort implementuje jednoduchý algoritmus řazení takto:

• Algoritmus opakovaně hledá nejnižší prvek.
• Vyměňte aktuální prvek za prvek s nejnižší hodnotou
• S každou iterací/průchodem druhu výběru se prvky vymění.

Každý průchod proto zpracovává řada jako dvě oblasti: seřazený blok, který roste zleva, a neseřazený blok, který se zmenšuje zprava. Algoritmus prochází neseřazený blok, pamatuje si index nejmenší hodnoty, kterou narazí, a tuto hodnotu vymění s první neseřazenou pozicí.

Protože v jednom průchodu dochází pouze k jedné výměně, pole n prvků je seřazeno po maximálně n-1 výměnách. Tato vlastnost odlišuje tuto rutinu od ostatních rutin pro začátečníky. Java třídicí algoritmy, které přesouvají data mnohem častěji.

Jedno tracNásledující text následuje za vzorovým polem {860, 8, 200, 9} přesně tak, jak ho program v následující části vytiskne za běhu.

Dva detaily v tom tracStojí za to se u nich zastavit. Zaprvé, i ve 3. průchodu se stále hlásí výměna, i když se pořadí nezmění, protože nejmenší zbývající hodnota se již nachází na aktuálním indexu a program si prvek vymění sám se sebou. Zadruhé, počet porovnání se v každém průchodu sníží o jedno (tři, pak dvě, pak jedna), což je vzorec, který odpovídá údajům o složitosti uvedeným dále na stránce.

Java Program pro implementaci třídění výběru

Níže uvedená třída se jmenuje SelectionSortAlgo a nachází se v balíčku com.guru99. Metoda main() deklaruje vzorové pole, vypíše ho, předá ho metodě selection() k seřazení a znovu ho vypíše. Pomocná metoda printArray() zapíše všechny prvky na jeden řádek, což vytvoří čitelný protokol pass-by-pass.

Uvnitř selection() vnější smyčka označuje hranici mezi seřazenými a neseřazenými oblastmi, proměnná index drží pozici nejmenší dosud viděné hodnoty a tři přiřazení na konci každého průchodu provádějí záměnu.

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

Výstup:

Kompilace a spuštění třídy vygeneruje níže uvedený protokol konzole s jedním blokem výstupu na průchod.

------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

Začátečníky při prvním spuštění tohoto příkladu zaskočí dva problémy. Protože soubor deklaruje package com.guru99;, zdroj musí existovat v odpovídajícím com/guru99 adresář, jinak kompilátor hlásí neshodu názvů balíčků nebo tříd. Třída musí být pak spuštěna pod svým plně kvalifikovaným názvem, java com.guru99.SelectionSortAlgo, protože prostý java SelectionSortAlgo vyvolává NoClassDefFoundError.

Další častou pastí jsou hranice smyčky. Vnější smyčka končí v array.length - 1 a vnitřní smyčka začíná na i + 1; změna kterékoli z hranic vyvolá další prázdný průchod nebo výjimku ArrayIndexOutOfBoundsException.

Časová a prostorová složitost výběrového řazení

Vnitřní smyčka v programu vždy běží na konec pole, takže algoritmus provádí stejný počet porovnání bez ohledu na to, jak data vypadají. Pro pole o n prvcích je tento součet n(n-1)/2, což pro čtyřprvkový vzorek se rovná šesti, a výstup výše skutečně vytiskne přesně šest porovnávacích řádků.

Z této jednotné řady čísel vyplývají tři důsledky:

• Výběrové řazení není adaptivní. Seřazený vstup stojí přesně tolik jako obrácený vstup, takže neexistuje žádná zkratka s předčasným ukončením tohoto typu. bublinové řazení nabízí.
• Počet výměn je silnou stránkou algoritmu. Proběhne maximálně n-1 výměn, což je mnohem méně než kvadratický počet tahů, které mohou provést jiné jednoduché typy.
• Využití paměti je konstantní. Potřebné jsou pouze čítače smyček a dvě dočasné proměnné index a smallerNumber, takže pomocný prostor je O(1) a řazení probíhá na místě.

Praktickým limitem je kvadratický růst. Zdvojnásobení velikosti pole zhruba čtyřnásobně zvýší porovnávací práci, takže výběrové řazení je vhodné spíše pro výuku, malá pole a vložený kód než pro produkční datové sady, kde jsou správnou volbou algoritmy O(n log n).

Výhody a nevýhody výběrového řazení

Pochopení toho, kde algoritmus pomáhá a kde škodí, usnadňuje rozhodnutí, kdy je rozumné ho použít.

Výhody

• Logika je krátká a čitelná, a proto se jedná o standardní cvičení pro první třídění vedle řazení řazení.
• Řadí se na místě, takže se nepřiděluje žádné druhé pole a využití paměti se vstupem neroste.
• Provede maximálně n-1 zápisů do pole, což je důležité pro úložiště, kde jsou zápisy pomalé nebo opotřebovávají médium.
• Jeho doba běhu je zcela předvídatelná, protože počet porovnání závisí pouze na délce pole.

Nevýhody

• Každý případ je O(n²), takže algoritmus se neškáluje na velké kolekce.
• Nedokáže detekovat již seřazené pole, a proto nikdy nedokončí předčasně.
• Klasický tvar uvedený výše je nestabilní, takže dvě stejné hodnoty se mohou ocitnout v opačném pořadí.
• Porovnává častěji než řazení vložením na téměř uspořádaných datech, kde se řazení vložením blíží lineárnímu času.

Stručně řečeno, zvolte výběrové řazení, když je pole malé a každý zápis je nákladný, a vyhněte se mu, kdykoli je datová sada velká nebo již téměř seřazená.

Výběrové řazení vs. Bubble-řazení vs. řazení vkládáním

Všechny tři algoritmy jsou kvadratické, srovnávací metody na místě, ale chovají se odlišně, jakmile se změní tvar vstupu.

Tabulka vysvětluje běžnou odpověď z pohovoru. Výběrové řazení vítězí v počtu výměn, bublinové řazení vítězí v rozpoznávání již seřazeného vstupu a řazení vkládáním je v praxi obvykle nejrychlejší z těchto tří, protože reálná data jsou často částečně seřazena. Žádné z nich nekonkuruje řazení slučováním nebo rychlému řazení, jakmile pole naroste nad několik desítek prvků.

Nejčastější dotazy