Udvalg Sortering i Java Program med eksempel

Hvordan fungerer Selection Sort?

Selection Sort implementerer en simpel sorteringsalgoritme som følger:

• Algoritmen søger gentagne gange efter det laveste element.
• Skift det nuværende element med et element med den laveste værdi
• Ved hver iteration/gennemgang af udvælgelsessortering, skiftes elementer.

Hvert gennemløb behandler derfor matrix som to regioner: en sorteret blok, der vokser fra venstre, og en usorteret blok, der krymper til højre. Algoritmen gennemgår den usorterede blok, husker indekset for den mindste værdi, den møder, og udveksler denne værdi med den første usorterede position.

Fordi der kun sker én udveksling pr. gennemløb, ordnes et array af n elementer efter højst n-1 udvekslinger. Det er denne egenskab, der adskiller denne rutine fra de andre rutiner på begynderniveau. Java sorteringsalgoritmer, som flytter data langt oftere.

tracFigur e nedenfor følger eksempelmatrixen {860, 8, 200, 9} præcis som programmet i næste afsnit udskriver den under kørsel.

To detaljer i det tracDet er værd at holde en pause ved dem. For det første rapporterer gennemgang 3 stadig en ombytning, selvom rækkefølgen ikke ændres, fordi den mindste resterende værdi allerede befinder sig ved det aktuelle indeks, og programmet udveksler elementet med sig selv. For det andet falder antallet af sammenligninger med én ved hver gennemgang (tre, derefter to, derefter én), hvilket er mønsteret bag kompleksitetstallene længere nede på siden.

Java Program til at implementere Selection Sort

Klassen nedenfor hedder SelectionSortAlgo og findes i pakken com.guru99. main()-metoden deklarerer eksempelarrayet, udskriver det, sender det til selection() til sortering og udskriver det igen. Hjælperen printArray() skriver alle elementer på en enkelt linje, hvilket er det, der producerer den læsbare pass-by-pass-log.

Inde i selection() markerer den ydre løkke grænsen mellem de sorterede og usorterede områder, variabelindekset holder positionen for den mindste værdi, der er set indtil videre, og de tre tildelinger i slutningen af ​​hver gennemgang udfører ombytningen.

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

Output:

Kompilering og kørsel af klassen producerer konsolloggen nedenfor med én blok output pr. gennemløb.

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

To problemer fanger begyndere, når de kører dette eksempel for første gang. Fordi filen deklarerer package com.guru99;, kilden skal leve i en matchende com/guru99 mappe, ellers rapporterer compileren en uoverensstemmelse mellem pakke- eller klassenavn. Klassen skal derefter startes med sit fuldt kvalificerede navn, java com.guru99.SelectionSortAlgo, fordi almindelig java SelectionSortAlgo rejser NoClassDefFoundError.

Løkkegrænserne er den anden almindelige fælde. Den ydre løkke stopper ved array.length - 1 og den indre løkke starter kl. i + 1; ændring af en af ​​grænserne producerer et ekstra tomt gennemløb eller en ArrayIndexOutOfBoundsException.

Tids- og rumkompleksitet af selektionssortering

Den indre løkke i programmet kører altid til slutningen af ​​arrayet, så algoritmen udfører det samme antal sammenligninger, uanset hvordan dataene ser ud. For et array af n elementer er summen n(n-1)/2, hvilket for prøven med fire elementer er lig med seks, og outputtet ovenfor udskriver faktisk præcis seks sammenligningslinjer.

Tre konsekvenser følger af den ensartede række af tal:

• Sortering af udvalg er ikke adaptiv. Sorteret input koster præcis lige så meget som omvendt input, så der er ingen genvej til tidlig exit af den slags. boble sortering tilbud.
• Antallet af bytter er algoritmens stærke punkt. Der finder højst n-1 bytter sted, hvilket er langt færre end det kvadratiske antal træk, som andre simple sorteringer kan foretage.
• Hukommelsesforbruget er konstant. Kun løkketællerne og de to midlertidige variabler index og smallerNumber er nødvendige, så hjælperummet er O(1), og sorteringen sker på stedet.

Den kvadratiske vækst er den praktiske grænse. Fordobling af arraystørrelsen firedobler omtrent sammenligningsarbejdet, så sortering af udvalg er mere egnet til undervisning, små arrays og indlejret kode end produktionsdatasæt, hvor O(n log n) algoritmer er det rigtige valg.

Fordele og ulemper ved selektionssortering

At forstå, hvor algoritmen hjælper, og hvor den gør ondt, gør det lettere at afgøre, hvornår det er rimeligt at række ud efter den.

Fordele

• Logikken er kort og læsbar, hvilket er grunden til, at det er en standard første sorteringsøvelse sideløbende med indsætnings sortering.
• Den sorterer på stedet, så der allokeres ikke et andet array, og hukommelsesforbruget vokser ikke med inputtet.
• Den udfører højst n-1 skrivninger til arrayet, hvilket er vigtigt på storage, hvor skrivninger er langsomme eller slider på mediet.
• Dens køretid er fuldstændig forudsigelig, fordi sammenligningsantallet kun afhænger af arrayets længde.

Ulemper

• Hvert tilfælde er O(n²), så algoritmen skalerer ikke til store samlinger.
• Den kan ikke registrere et allerede sorteret array og afslutter derfor aldrig for tidligt.
• Den klassiske form vist ovenfor er ustabil, så to lige værdier kan ende i den modsatte rækkefølge.
• Den sammenligner oftere end indsættelsessortering på næsten ordnede data, hvor indsættelsessortering nærmer sig lineær tid.

Kort sagt, vælg sorteringssortering, når arrayet er lille, og hver skrivning er dyr, og undgå det, når datasættet er stort eller allerede tæt på sortering.

Sortering i forhold til udvalg Bubble-sortering vs. indsættelsessortering

Alle tre algoritmer er kvadratiske, på stedet sammenligningstyper, men de opfører sig forskelligt, når formen på inputtet ændrer sig.

Tabellen forklarer et almindeligt interviewsvar. Udvælgelsessortering vinder på antallet af udvekslinger, boblesortering vinder på genkendelse af input, der allerede er ordnet, og indsættelsessortering er normalt den hurtigste af de tre i praksis, fordi reelle data ofte er delvist sorteret. Ingen af ​​dem konkurrerer med mergesortering eller quicksortering, når arrayet vokser forbi et par dusin elementer.

Ofte Stillede Spørgsmål