Utvalg Sorterer inn Java Program med eksempel

Hvordan fungerer utvalgssortering?

Selection Sort implementerer en enkel sorteringsalgoritme som følger:

• Algoritmen søker gjentatte ganger etter det laveste elementet.
• Bytt gjeldende element med et element som har den laveste verdien
• Med hver iterasjon/passering av utvalgssortering, byttes elementer.

Hvert pass behandler derfor matrise som to regioner: en sortert blokk som vokser fra venstre og en usortert blokk som krymper til høyre. Algoritmen går gjennom den usorterte blokken, husker indeksen for den minste verdien den møter, og bytter den verdien med den første usorterte posisjonen.

Fordi bare én utveksling skjer per omgang, blir en matrise med n elementer ordnet etter maksimalt n-1 bytter. Det er denne egenskapen som skiller denne rutinen fra de andre rutinene på nybegynnernivå. Java sorteringsalgoritmer, som flytter data mye oftere.

Ocuco trace nedenfor følger eksempelmatrisen {860, 8, 200, 9} nøyaktig slik programmet i neste avsnitt skriver den ut under kjøretid.

To detaljer i det tracDet er verdt å stoppe opp. For det første rapporterer gjennomgang 3 fortsatt en bytte selv om rekkefølgen ikke endres, fordi den minste gjenværende verdien allerede er på gjeldende indeks og programmet bytter elementet med seg selv. For det andre faller antallet sammenligninger med én på hver gjennomgang (tre, deretter to, deretter én), som er mønsteret bak kompleksitetstallene lenger ned på siden.

Java Program for å implementere Selection Sort

Klassen nedenfor heter SelectionSortAlgo og ligger i pakken com.guru99. main()-metoden deklarerer eksempelarrayet, skriver det ut, gir det til selection() for sortering og skriver det ut på nytt. Hjelpefunksjonen printArray() skriver alle elementene på én linje, som er det som produserer den lesbare pass-by-pass-loggen.

Inne i selection() markerer den ytre løkken grensen mellom de sorterte og usorterte områdene, variabelindeksen holder posisjonen til den minste verdien som er sett så langt, og de tre tildelingene på slutten av hver omgang utfører byttet.

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

Utgang:

Kompilering og kjøring av klassen produserer konsollloggen nedenfor, med én blokk med 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

To problemer fanger nybegynnere når de kjører dette eksemplet for første gang. Fordi filen deklarerer package com.guru99;, kilden må befinne seg i en samsvarende com/guru99 katalog, ellers rapporterer kompilatoren en feilmatching av pakke- eller klassenavn. Klassen må da startes med sitt fullstendige navn, java com.guru99.SelectionSortAlgo, fordi vanlig java SelectionSortAlgo hever NoClassDefFoundError.

Løkkegrensene er den andre vanlige fellen. Den ytre løkken stopper ved array.length - 1 og den indre sløyfen starter kl. i + 1; endring av en av grensene produserer et ekstra tomt pass eller en ArrayIndexOutOfBoundsException.

Tids- og romkompleksitet ved utvalgssortering

Den indre løkken i programmet går alltid til slutten av tabellen, så algoritmen utfører samme antall sammenligninger uansett hvordan dataene ser ut. For en tabell med n elementer er summen n(n-1)/2, som for prøven med fire elementer er lik seks, og resultatet ovenfor skriver faktisk ut nøyaktig seks sammenligningslinjer.

Tre konsekvenser følger av den ensartede rekken med tall:

• Sortering av utvalg er ikke adaptiv. Sortert inndata koster nøyaktig like mye som omvendt inndata, så det finnes ingen snarvei til tidlig avslutning av den typen. boblesortering tilbud.
• Bytteantall er algoritmens sterke punkt. På det meste finner n-1 bytter sted, noe som er langt færre enn det kvadratiske antallet trekk andre enkle sorteringer kan gjøre.
• Minnebruken er konstant. Bare løkketellerne og de to midlertidige variablene index og smallerNumber er nødvendige, så hjelperommet er O(1) og sorteringen skjer på stedet.

Den kvadratiske veksten er den praktiske grensen. Dobling av arraystørrelsen firedobler omtrent sammenligningsarbeidet, så utvalgssortering passer bedre til undervisning, små arrayer og innebygd kode enn produksjonsdatasett, der O(n log n) algoritmer er det riktige valget.

Fordeler og ulemper med utvalgssortering

Å forstå hvor algoritmen hjelper og hvor den skader gjør det lettere å avgjøre når det er rimelig å strekke seg etter den.

Fordeler

• Logikken er kort og lesbar, og det er derfor det er en standard første sorteringsøvelse ved siden av innsettings sortering.
• Den sorterer på plass, så ingen andre array blir tildelt og minnebruken vokser ikke med inputen.
• Den utfører maksimalt n-1 skrivinger til arrayet, noe som er viktig på lagring der skrivingene er trege eller sliter ut mediet.
• Kjøretiden er fullstendig forutsigbar, fordi sammenligningsantallet bare avhenger av arraylengden.

Ulemper

• Hvert tilfelle er O(n²), så algoritmen skalerer ikke til store samlinger.
• Den kan ikke oppdage en allerede sortert matrise og fullføres derfor aldri for tidlig.
• Den klassiske formen vist ovenfor er ustabil, så to like verdier kan ende opp i motsatt rekkefølge.
• Den sammenligner oftere enn innsettingssortering på nesten ordnede data, der innsettingssortering nærmer seg lineær tid.

Kort sagt, velg utvalgssortering når arrayet er lite og hver skriving er dyr, og unngå det når datasettet er stort eller allerede nær sortering.

Utvalg Sortering vs. Bubble-sortering vs. innsettingssortering

Alle tre algoritmene er kvadratiske, på-sted-sammenligningstyper, men de oppfører seg annerledes når formen på inngangen endres.

Tabellen forklarer et vanlig intervjusvar. Utvalgssortering vinner på antall utvekslinger, boblesortering vinner på gjenkjenning av input som allerede er ordnet, og innsettingssortering er vanligvis den raskeste av de tre i praksis fordi reelle data ofte er delvis sortert. Ingen av dem konkurrerer med mergesortering eller quicksortering når arrayet vokser forbi noen få dusin elementer.

Spørsmål og svar