Urval Sortera in Java Program med exempel

Hur fungerar urvalssortering?

Selection Sort implementerar en enkel sorteringsalgoritm enligt följande:

• Algoritmen söker upprepade gånger efter det lägsta elementet.
• Byt aktuellt element med ett element som har det lägsta värdet
• Med varje iteration/pass av urvalssort byts element.

Varje pass behandlar därför array som två regioner: ett sorterat block som växer från vänster och ett osorterat block som krymper till höger. Algoritmen går igenom det osorterade blocket, kommer ihåg indexet för det minsta värde det möter och byter ut det värdet med den första osorterade positionen.

Eftersom endast ett utbyte sker per pass, ordnas en array av n element efter högst n-1 utbyten. Det är den egenskapen som skiljer denna rutinen från de andra nybörjarnivårutinerna. Java sorteringsalgoritmer, som flyttar data mycket oftare.

Ocuco-landskapet trace nedan följer exempelmatrisen {860, 8, 200, 9} exakt så som programmet i nästa avsnitt skriver ut den vid körning.

Två detaljer i det tracDet är värt att pausa vid dem. För det första rapporterar pass 3 fortfarande ett byte även om ordningen inte ändras, eftersom det minsta återstående värdet redan finns vid det aktuella indexet och programmet byter elementet med sig självt. För det andra minskar antalet jämförelser med ett vid varje pass (tre, sedan två, sedan en), vilket är mönstret bakom komplexitetssiffrorna längre ner på sidan.

Java Program för att implementera urvalssortering

Klassen nedan heter SelectionSortAlgo och finns i paketet com.guru99. main()-metoden deklarerar exempelarrayen, skriver ut den, skickar den till selection() för sortering och skriver ut den igen. Hjälparen printArray() skriver alla element på en enda rad, vilket är det som producerar den läsbara pass-by-pass-loggen.

Inuti selection() markerar den yttre loopen gränsen mellan de sorterade och osorterade områdena, variabelindexet håller positionen för det minsta värdet som hittills setts, och de tre tilldelningarna i slutet av varje omgång utför växlingen.

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

Produktion:

Att kompilera och köra klassen producerar konsolloggen nedan, med ett block utdata per pass.

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

Två problem överraskar nybörjare när de kör det här exemplet för första gången. Eftersom filen deklarerar package com.guru99;, källan måste finnas i en matchande com/guru99 katalog, annars rapporterar kompilatorn en matchning mellan paket- eller klassnamn. Klassen måste då startas med sitt fullständiga namn, java com.guru99.SelectionSortAlgo, eftersom vanligt java SelectionSortAlgo genererar NoClassDefFoundError.

Loopgränserna är den andra vanliga fällan. Den yttre loopen stannar vid array.length - 1 och den inre slingan börjar kl. i + 1; om man ändrar endera gränsen produceras ett extra tomt pass eller ett ArrayIndexOutOfBoundsException.

Tids- och rumskomplexitet för urvalssortering

Den inre loopen i programmet körs alltid till slutet av arrayen, så algoritmen utför samma antal jämförelser oavsett hur data ser ut. För en array med n element är den totala mängden n(n-1)/2, vilket för urvalet med fyra element är lika med sex, och utdata ovan skriver faktiskt ut exakt sex jämförelserader.

Tre konsekvenser följer av den enhetliga raden av siffror:

• Sortering av urval är inte adaptiv. Sorterad inmatning kostar exakt lika mycket som omvänd inmatning, så det finns ingen genväg för tidig avstängning av det slaget. bubbelsorter erbjudanden.
• Antalet byten är algoritmens styrka. Som mest sker n-1 byten, vilket är betydligt färre än det kvadratiska antalet drag som andra enkla sorteringar kan göra.
• Minnesanvändningen är konstant. Endast loopräknarna och de två temporära variablerna index och smallerNumber behövs, så hjälputrymmet är O(1) och sorteringen sker på plats.

Den kvadratiska tillväxten är den praktiska gränsen. Att fördubla arraystorleken fyrdubblar ungefär jämförelsearbetet, så urvalssortering passar undervisning, små arrayer och inbäddad kod snarare än produktionsdatauppsättningar, där O(n log n) algoritmer är det rätta valet.

Fördelar och nackdelar med urvalssortering

Att förstå var algoritmen hjälper och var den gör ont gör det lättare att avgöra när det är rimligt att använda den.

Fördelar

• Logiken är kort och lättläst, vilket är anledningen till att det är en standard första sorteringsövning vid sidan av insättningssortering.
• Den sorterar på plats, så ingen andra array allokeras och minnesanvändningen växer inte med indata.
• Den utför som mest n-1 skrivningar till arrayen, vilket är viktigt vid lagring där skrivningarna är långsamma eller sliter ut mediet.
• Dess körtid är helt förutsägbar, eftersom jämförelseantalet endast beror på arraylängden.

Nackdelar

• Varje fall är O(n²), så algoritmen skalar inte till stora samlingar.
• Den kan inte upptäcka en redan sorterad array och avslutas därför aldrig för tidigt.
• Den klassiska formen som visas ovan är instabil, så två lika värden kan hamna i motsatt ordning.
• Den jämför oftare än insättningssortering på nästan ordnad data, där insättningssortering närmar sig linjär tid.

Kort sagt, välj sorteringssortering när arrayen är liten och varje skrivning är dyr, och undvik det när datamängden är stor eller redan nära sortering.

Sortera urval vs. Bubble-sortering kontra insättningssortering

Alla tre algoritmerna är kvadratiska, på plats jämförelsetyper, men de beter sig olika när ingångens form ändras.

Tabellen förklarar ett vanligt intervjusvar. Urvalssortering vinner på antalet utbyten, bubbelsortering vinner på att känna igen inmatning som redan är ordnad, och insättningssortering är vanligtvis den snabbaste av de tre i praktiken eftersom verklig data ofta är delvis sorterad. Ingen av dem konkurrerar med sammanslagningssortering eller snabbsortering när arrayen växer förbi några dussin element.

Vanliga frågor