Selectie Sorteren Java Programma met voorbeeld

Door: James Hartman James Hartman
Hours Bijgewerkt

⚡ Slimme samenvatting

Selectiesortering in Java Het programma scant herhaaldelijk het ongesorteerde deel van een array, vindt de kleinste resterende waarde en verwisselt deze met de juiste positie. De bewerking is voltooid met maximaal n-1 wisselingen, ongeacht de volgorde van de invoer.

  • 🔘 Definitie: Bij elke doorgang van de selectiesorteermethode wordt de array opgedeeld in een gesorteerd gedeelte en een ongesorteerd gedeelte.
  • ☑️ Werkwijze: Elke doorgang doorzoekt het ongesorteerde gebied naar het laagste element en schuift dit naar voren.
  • ✅ Programma: De Java Het voorbeeld sorteert {860, 8, 200, 9} en print elke vergelijking en verwisseling.
  • 🧪 complexiteit: De beste, gemiddelde en slechtste gevallen hebben allemaal een looptijd van O(n²), omdat het aantal vergelijkingen nooit afneemt.
  • ️ Geheugen: De uitwisselingen vinden plaats binnen de oorspronkelijke array, waardoor de extra ruimte O(1) blijft.
  • 📊 Gedrag: De klassieke versie is instabiel, maar voert wel de minste schrijfbewerkingen uit van alle kwadratische sorteermethoden.
Meer informatie

Selectie Sorteren Java Programma met voorbeeld

Hoe werkt Selectie Sorteren?

Selection Sort implementeert als volgt een eenvoudig sorteeralgoritme:

  • Algoritme zoekt herhaaldelijk naar het laagste element.
  • Verwissel het huidige element met een element met de laagste waarde
  • Bij elke iteratie/passage van selectiesortering worden elementen verwisseld.

Elke doorgang behandelt daarom de reeks Het algoritme bestaat uit twee gebieden: een gesorteerd blok dat van links naar rechts groeit en een ongesorteerd blok dat van rechts naar links krimpt. Het algoritme doorloopt het ongesorteerde blok, onthoudt de index van de kleinste waarde die het tegenkomt en wisselt die waarde om met de eerste positie in het ongesorteerde blok.

Omdat er per keer maar één uitwisseling plaatsvindt, is een array van n elementen na maximaal n-1 uitwisselingen geordend. Die eigenschap onderscheidt deze routine van de andere routines voor beginners. Java sorteeralgoritmen, die gegevens veel vaker verplaatsen.

De tracHieronder volgt de voorbeeldreeks {860, 8, 200, 9} precies zoals het programma in de volgende sectie deze tijdens de uitvoering afdrukt.

Passeren Vergelijkingen afgedrukt Kleinste waarde gevonden Array na de swap
Start - - 860 8 200 9
1 860 en 8, 8 en 200, 8 en 9 8 8 860 200 9
2 860 en 200, 200 en 9 9 8 9 200 860
3 200 en 860 200 8 9 200 860

Twee details daarin tracHet is de moeite waard om even stil te staan ​​bij de volgende punten. Ten eerste meldt stap 3 nog steeds een verwisseling, ook al verandert de volgorde niet, omdat de kleinste resterende waarde zich al op de huidige index bevindt en het programma het element met zichzelf verwisselt. Ten tweede neemt het aantal vergelijkingen bij elke stap met één af (eerst drie, dan twee, dan één), wat het patroon verklaart achter de complexiteitscijfers verderop op deze pagina.

Java Programma om Selection Sort te implementeren

De onderstaande klasse heet SelectionSortAlgo en bevindt zich in het pakket com.guru99. De main()-methode declareert de voorbeeldarray, print deze, geeft deze door aan selection() om te sorteren en print deze vervolgens opnieuw. De hulpfunctie printArray() schrijft alle elementen op één regel, wat resulteert in het leesbare stapsgewijze logboek.

Binnen de `selection()`-functie markeert de buitenste lus de grens tussen het gesorteerde en het ongesorteerde gebied, de variabele `index` bevat de positie van de tot nu toe geziene kleinste waarde, en de drie toewijzingen aan het einde van elke iteratie voeren de verwisseling uit.

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:

Het compileren en uitvoeren van de klasse produceert de onderstaande console-uitvoer, met één uitvoerblok per iteratie.

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

Twee problemen komen beginners vaak tegen wanneer ze dit voorbeeld voor het eerst uitvoeren. Omdat het bestand declareert... package com.guru99;De bron moet zich in een overeenkomstige omgeving bevinden. com/guru99 De map moet anders worden aangeroepen, anders meldt de compiler een onjuiste pakket- of klassenaam. De klasse moet dan worden gestart met de volledig gekwalificeerde naam. java com.guru99.SelectionSortAlgo, omdat gewoon java SelectionSortAlgo Geeft een NoClassDefFoundError.

De lusgrenzen zijn een andere veelvoorkomende valkuil. De buitenste lus stopt bij array.length - 1 en de binnenste lus begint bij i + 1Het wijzigen van een van beide grenzen resulteert in een extra lege doorgang of een ArrayIndexOutOfBoundsException.

GERELATEERDE ARTIKELEN

Tijd- en ruimtecomplexiteit van selectiesortering

De binnenste lus in het programma loopt altijd tot het einde van de array, waardoor het algoritme hetzelfde aantal vergelijkingen uitvoert, ongeacht hoe de gegevens eruitzien. Voor een array met n elementen is dat totaal n(n-1)/2, wat voor het voorbeeld met vier elementen gelijk is aan zes, en de bovenstaande uitvoer print inderdaad precies zes regels met "Vergelijken".

SITUATIE vergelijkingen swaps Tijdcomplexiteit Hulpruimte
Beste (array is al gesorteerd) n(n-1)/2 n-1 O(n²) O (1)
Gemiddelde (willekeurige volgorde) n(n-1)/2 n-1 O(n²) O (1)
Slechtste (in omgekeerde volgorde) n(n-1)/2 n-1 O(n²) O (1)

Uit die uniforme reeks cijfers volgen drie consequenties:

  • Selectiesortering is niet adaptief. Gesorteerde invoer kost precies evenveel als omgekeerde invoer, dus er is geen mogelijkheid om vroegtijdig te stoppen. bellen sorteren biedt.
  • Het aantal wisselingen is het sterke punt van het algoritme. Er vinden maximaal n-1 wisselingen plaats, wat veel minder is dan het kwadratische aantal zetten dat andere eenvoudige sorteeralgoritmes kunnen maken.
  • Het geheugengebruik is constant. Alleen de lusstellers en de twee tijdelijke variabelen index en smallerNumber zijn nodig, dus de hulpruimte is O(1) en de sortering vindt ter plaatse plaats.

De kwadratische groei is de praktische limiet. Het verdubbelen van de arraygrootte verviervoudigt ruwweg het aantal vergelijkingen, waardoor selectiesortering geschikt is voor onderwijsdoeleinden, kleine arrays en ingebedde code, in plaats van voor productiedatasets, waar O(n log n)-algoritmen de juiste keuze zijn.

Voordelen en nadelen van selectiesortering

Door te begrijpen waar het algoritme helpt en waar het schaadt, wordt het makkelijker om te bepalen wanneer het zinvol is om het te gebruiken.

Voordelen

  • De logica is kort en bondig, waardoor het een standaard eerste sorteeroefening is, samen met invoegsoort.
  • Het sorteert op dezelfde plek, waardoor er geen tweede array wordt aangemaakt en het geheugengebruik niet toeneemt met de invoer.
  • Het voert maximaal n-1 schrijfbewerkingen naar de array uit, wat van belang is bij opslag waar schrijfbewerkingen traag zijn of het medium slijten.
  • De looptijd is volledig voorspelbaar, omdat het aantal vergelijkingen alleen afhangt van de lengte van de array.

Nadelen

  • Elk geval is O(n²), dus het algoritme is niet schaalbaar naar grote verzamelingen.
  • Het kan een reeds gesorteerde array niet detecteren en eindigt daarom nooit voortijdig.
  • De klassieke vorm die hierboven is weergegeven, is instabiel, waardoor twee gelijke waarden in de omgekeerde volgorde kunnen terechtkomen.
  • Het vergelijkt vaker dan insertion sort op bijna geordende data, waarbij insertion sort een lineaire tijdscomplexiteit benadert.

Kortom, kies voor selectiesortering wanneer de array klein is en elke schrijfbewerking veel rekenkracht vereist, en vermijd het wanneer de dataset groot is of al bijna gesorteerd is.

Selectiesortering versus Bubble Sort versus Insertion Sort

Alle drie de algoritmen zijn kwadratische, in-place vergelijkingssorteeralgoritmen, maar ze gedragen zich anders zodra de vorm van de invoer verandert.

Criterium Selectie sorteren Bubble soort Invoegsortering
gunstigste tijd O(n²) O (n) O (n)
Gemiddelde en worstcasetijd O(n²) O(n²) O(n²)
Ruilen of verschuiven in het ergste geval. n-1 swaps n(n-1)/2 swaps Tot n(n-1)/2 verschuivingen
Stal Nee Ja Ja
Past zich aan gesorteerde invoer aan Nee Ja Ja
Hulpruimte O (1) O (1) O (1)
Typisch gebruik Minimaal aantal schrijfbewerkingen vereist Het aanleren en herkennen van gesorteerde gegevens Kleine of bijna gesorteerde arrays

De tabel illustreert een veelvoorkomend antwoord tijdens sollicitatiegesprekken. Selectiesortering wint op het gebied van het aantal uitwisselingen, bubbelsortering wint op het gebied van het herkennen van reeds geordende invoer, en invoegsortering is in de praktijk meestal de snelste van de drie omdat echte data vaak gedeeltelijk gesorteerd is. Geen van deze methoden kan concurreren met samenvoegsortering of quicksort zodra de array groter wordt dan een paar dozijn elementen.

Veelgestelde vragen

Na n-1 iteraties bevat het ongesorteerde gebied slechts één element, en dat ene element staat al op de juiste plaats. Nog een iteratie uitvoeren zou niets meer vergelijken, dus de luslimiet voorkomt een onnodige iteratie.

AI-assistenten kunnen elke stap in woorden beschrijven, extra testreeksen maken en het aantal vergelijkingen voor een gegeven invoer tellen. Gebruik de uitleg als studiehulpmiddel en controleer elke bewering over complexiteit aan de hand van een leerboek voordat je deze citeert.

Ja. GitHub-copiloot Voltooit de methode vanuit een handtekening of commentaar. Controleer zelf het begin van de binnenste lus en de swap-regels, omdat gegenereerde versies soms wisselen met i in plaats van met de opgeslagen minimumindex.

De hier getoonde versie is instabiel, omdat een ruil over een lange afstand ervoor kan zorgen dat een gelijke waarde voorbij een andere springt. Shifthet blok elementen verwisselen in plaats van te wisselenping Behoudt de oorspronkelijke volgorde van gelijke sleutels, ten koste van extra schrijfbewerkingen.

Reverse De vergelijking binnen de binnenste lus. Testen of array[j] groter is dan array[index]. tracks is de grootste resterende waarde, dus bij elke stap wordt het maximum naar voren geschoven en de voltooide array loopt van hoog naar laag.

Ja. Een recursieve methode vindt het minimum van de huidige subreeks, plaatst dit vooraan en roept zichzelf vervolgens aan op de rest. Het aantal vergelijkingen blijft ongewijzigd, maar de aanroepstack voegt O(n) ruimte toe, dus de lusvorm heeft de voorkeur.

De meest voorkomende fouten zijn het vergeten om de index aan het begin van elke iteratie terug te zetten naar i, het starten van de binnenste lus bij i in plaats van i + 1, en het verwisselen van elementen.ping array[j] in plaats van array[index], wat verlies oplevert track van de kleinste waarde.

Nee. Arrays.sort() past een dual-pivot quicksort toe op primitieve gegevenstypen en TimSort op objecten, met een insertion-style sort op kleine partities. Selection sort komt voor in lesmateriaal en handgeschreven code, maar niet in de standaardbibliotheek.

Vat dit bericht samen met: