Auswahl Sortierung in Java Programm mit Beispiel

⚡ Intelligente Zusammenfassung

Auswahlsortierung in Java durchsucht wiederholt den unsortierten Teil eines Arrays, findet den kleinsten verbleibenden Wert und tauscht ihn an die richtige Position. Die Arbeit wird mit höchstens n-1 Vertauschungen abgeschlossen, unabhängig von der Eingabereihenfolge.

  • 🔘 Definition: Beim Selection Sort wird das Array bei jedem Durchlauf in einen sortierten und einen unsortierten Bereich aufgeteilt.
  • ☑️ Verarbeiten: Bei jedem Durchlauf wird der unsortierte Bereich nach dem kleinsten Element durchsucht und dieses dann nach vorne verschoben.
  • ✅ Programm (kann in Englisch und Deutsch durchgefuehrt werden) Das Java Beispiel sortiert {860, 8, 200, 9} und gibt jeden Vergleich und jede Vertauschung aus.
  • 🧪 Komplexität: Im besten, durchschnittlichen und schlechtesten Fall beträgt die Laufzeit jeweils O(n²), da die Anzahl der Vergleiche nie abnimmt.
  • ️ Erinnerung: Der Austausch erfolgt innerhalb des ursprünglichen Arrays, sodass der zusätzliche Speicherplatz bei O(1) bleibt.
  • 📊 Verhalten: Die klassische Version ist instabil, benötigt aber von allen quadratischen Sortieralgorithmen die wenigsten Schreibvorgänge.

Auswahl Sortierung in Java Programm mit Beispiel

Wie funktioniert die Auswahlsortierung?

Selection Sort implementiert einen einfachen Sortieralgorithmus wie folgt:

  • Der Algorithmus sucht wiederholt nach dem niedrigsten Element.
  • Tauschen Sie das aktuelle Element gegen ein Element mit dem niedrigsten Wert aus
  • Bei jeder Iteration/Durchlauf der Auswahlsortierung werden Elemente ausgetauscht.

Jeder Durchgang behandelt daher den Array Das System besteht aus zwei Bereichen: einem sortierten Block, der von links wächst, und einem unsortierten Block, der von rechts schrumpft. Der Algorithmus durchläuft den unsortierten Block, merkt sich den Index des kleinsten gefundenen Wertes und vertauscht diesen Wert mit der ersten Position im unsortierten Block.

Da pro Durchlauf nur ein Tauschvorgang stattfindet, ist ein Array mit n Elementen nach höchstens n-1 Tauschvorgängen sortiert. Diese Eigenschaft unterscheidet diese Routine von anderen Routinen für Anfänger. Java Sortieralgorithmen, die Daten viel häufiger verschieben.

Das tracIm Folgenden wird das Beispiel-Array {860, 8, 200, 9} genau so dargestellt, wie es das Programm im nächsten Abschnitt zur Laufzeit ausgibt.

Passieren gedruckte Vergleiche Kleinster gefundener Wert Array nach dem Tausch
Start - - 860 8 200 9
1 860 und 8, 8 und 200, 8 und 9 8 8 860 200 9
2 860 und 200, 200 und 9 9 8 9 200 860
3 200 und 860 zur Verfügung 200 8 9 200 860

Zwei Details dazu tracDiese Punkte sind einen genaueren Blick wert. Erstens meldet Durchlauf 3 immer noch einen Tausch, obwohl sich die Reihenfolge nicht ändert, da sich der kleinste verbleibende Wert bereits am aktuellen Index befindet und das Programm das Element mit sich selbst vertauscht. Zweitens sinkt die Anzahl der Vergleiche in jedem Durchlauf um eins (drei, dann zwei, dann eins), was das Muster hinter den Komplexitätsangaben weiter unten auf der Seite erklärt.

Java Programm zur Implementierung der Auswahlsortierung

Die unten stehende Klasse heißt SelectionSortAlgo und befindet sich im Paket com.guru99. Die main()-Methode deklariert das Beispiel-Array, gibt es aus, übergibt es an selection() zum Sortieren und gibt es erneut aus. Die Hilfsfunktion printArray() schreibt alle Elemente in eine einzige Zeile, wodurch das übersichtliche, schrittweise Protokoll entsteht.

Innerhalb von selection() markiert die äußere Schleife die Grenze zwischen dem sortierten und dem unsortierten Bereich, die Variable index speichert die Position des bisher kleinsten Wertes, und die drei Zuweisungen am Ende jedes Durchlaufs führen den Tausch durch.

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

Ausgang:

Das Kompilieren und Ausführen der Klasse erzeugt das unten stehende Konsolenprotokoll, wobei pro Durchlauf ein Ausgabeblock entsteht.

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

Zwei Probleme stoßen Anfänger beim ersten Ausführen dieses Beispiels häufig. Denn die Datei deklariert package com.guru99;Die Quelle muss sich in einem passenden com/guru99 Das Verzeichnis muss korrekt sein, andernfalls meldet der Compiler einen Paket- oder Klassennamenskonflikt. Die Klasse muss dann über ihren vollqualifizierten Namen aufgerufen werden. java com.guru99.SelectionSortAlgoweil schlicht java SelectionSortAlgo löst einen NoClassDefFoundError aus.

Die Schleifenbegrenzungen stellen eine weitere häufige Falle dar. Die äußere Schleife stoppt bei array.length - 1 und die innere Schleife beginnt bei i + 1Eine Änderung einer der beiden Grenzen führt entweder zu einem zusätzlichen leeren Durchlauf oder zu einer ArrayIndexOutOfBoundsException.

Zeit- und Speicherkomplexität des Selection Sort-Verfahrens

Die innere Schleife des Programms durchläuft immer das Ende des Arrays, sodass der Algorithmus unabhängig von der Datenstruktur immer die gleiche Anzahl an Vergleichen durchführt. Bei einem Array mit n Elementen beträgt diese Anzahl n(n-1)/2, was für das Beispiel mit vier Elementen sechs ergibt. Die obige Ausgabe zeigt tatsächlich genau sechs Vergleichszeilen an.

Case Vergleiche Swaps Zeitliche Komplexität Hilfsraum
best (Array bereits sortiert) n(n-1)/2 n-1 O(n²) O (1)
Durchschnitt (zufällige Reihenfolge) n(n-1)/2 n-1 O(n²) O (1)
Schlechteste (umgekehrt sortiert) n(n-1)/2 n-1 O(n²) O (1)

Aus dieser einheitlichen Zahlenreihe ergeben sich drei Konsequenzen:

  • Selection Sort ist nicht adaptiv. Sortierte Eingaben verursachen exakt die gleichen Kosten wie umgekehrte Eingaben, daher gibt es keine Abkürzung zum vorzeitigen Abbruch. Blase sortieren bietet an.
  • Die geringe Anzahl an Tauschvorgängen ist die Stärke des Algorithmus. Es finden maximal n-1 Tauschvorgänge statt, was deutlich weniger ist als die quadratische Anzahl an Schritten, die andere einfache Sortieralgorithmen durchführen können.
  • Der Speicherverbrauch ist konstant. Es werden lediglich die Schleifenzähler und die beiden temporären Variablen index und smallerNumber benötigt, daher ist der zusätzliche Speicherplatz O(1) und die Sortierung erfolgt direkt im Speicher.

Das quadratische Wachstum stellt die praktische Grenze dar. Eine Verdopplung der Arraygröße vervierfacht in etwa den Vergleichsaufwand, daher eignet sich Selection Sort eher für Lehrzwecke, kleine Arrays und eingebetteten Code als für Produktionsdatensätze, wo O(n log n)-Algorithmen die richtige Wahl sind.

Vor- und Nachteile des Selection Sort-Verfahrens

Wenn man versteht, wo der Algorithmus hilft und wo er schadet, wird es einfacher zu entscheiden, wann es sinnvoll ist, ihn einzusetzen.

Vorteile

  • Die Logik ist kurz und verständlich, weshalb sie eine standardmäßige erste Sortierübung darstellt. Sortieren durch Einfügen.
  • Es sortiert direkt am Speicher, sodass kein zweites Array allokiert wird und der Speicherverbrauch nicht mit der Eingabe wächst.
  • Es führt maximal n-1 Schreibvorgänge auf das Array durch, was bei Speichern von Bedeutung ist, bei denen Schreibvorgänge langsam sind oder das Medium verschleißen.
  • Die Laufzeit ist vollständig vorhersehbar, da die Anzahl der Vergleiche nur von der Arraylänge abhängt.

Nachteile

  • Jeder Fall hat eine Komplexität von O(n²), daher ist der Algorithmus für große Datenmengen nicht skalierbar.
  • Es kann ein bereits sortiertes Array nicht erkennen und beendet daher nie vorzeitig.
  • Die oben dargestellte klassische Form ist instabil, daher können zwei gleiche Werte in umgekehrter Reihenfolge vorliegen.
  • Es vergleicht häufiger als Insertion Sort bei nahezu geordneten Daten, wobei Insertion Sort eine lineare Laufzeit erreicht.

Kurz gesagt: Wählen Sie Selection Sort, wenn das Array klein ist und jeder Schreibvorgang teuer ist, und vermeiden Sie es, wenn der Datensatz groß oder bereits annähernd sortiert ist.

Auswahlsortierung vs. Bubble-Sort vs. Einfügungssortierung

Alle drei Algorithmen sind quadratische, In-Place-Vergleichssortierverfahren, verhalten sich jedoch unterschiedlich, sobald sich die Form der Eingabe ändert.

Kriterium Auswahl sortieren Bubble sort Sortieren durch Einfügen
Best-Case-Zeit O(n²) O (n) O (n)
Durchschnittliche und ungünstigste Zeit O(n²) O(n²) O(n²)
Tausch oder Verschiebung im schlimmsten Fall n-1-Tauschvorgänge n(n-1)/2 Vertauschungen Bis zu n(n-1)/2 Verschiebungen
Stabil Nein Ja Ja
Passt sich sortierten Eingaben an Nein Ja Ja
Hilfsraum O (1) O (1) O (1)
Typische Verwendung Die geringste Anzahl an Schreibvorgängen ist erforderlich Lehren und Erkennen sortierter Daten Kleine oder nahezu sortierte Arrays

Die Tabelle erläutert eine häufige Antwort in Vorstellungsgesprächen. Selection Sort ist am schnellsten, da weniger Vertauschungen nötig sind, Bubble Sort erkennt bereits sortierte Eingaben am besten, und Insertion Sort ist in der Praxis meist der schnellste der drei, da reale Daten oft nur teilweise sortiert sind. Keiner der drei kann mit Merge Sort oder Quicksort mithalten, sobald das Array einige Dutzend Elemente überschreitet.

Häufig gestellte Fragen

Nach n-1 Durchläufen enthält der unsortierte Bereich nur noch ein einziges Element, und dieses eine Element befindet sich bereits an seinem richtigen Platz. Ein weiterer Durchlauf würde keinen Vergleich mehr ermöglichen, daher vermeidet die Schleifenbegrenzung eine unnötige Iteration.

KI-Assistenten können jeden Durchlauf in Worten protokollieren, zusätzliche Testarrays erstellen und die Vergleiche für eine gegebene Eingabe zählen. Nutzen Sie die Erklärung als Lernhilfe und überprüfen Sie jede Behauptung zur Komplexität anhand eines Lehrbuchs, bevor Sie sie zitieren.

Ja. GitHub-Copilot Vervollständigt die Methode anhand einer Signatur oder eines Kommentars. Überprüfen Sie den Start der inneren Schleife und die Vertauschungszeilen selbst, da generierte Versionen manchmal mit i anstatt mit dem gespeicherten Minimalindex vertauschen.

Die hier gezeigte Version ist instabil, da bei einem Tausch über größere Distanzen ein gleicher Wert über einen anderen springen kann. Shiftden Block von Elementen anstatt zu tauschenping Die ursprüngliche Reihenfolge gleichartiger Schlüssel bleibt erhalten, allerdings auf Kosten zusätzlicher Schreibvorgänge.

Reverse Der Vergleich innerhalb der inneren Schleife. Es wird geprüft, ob array[j] größer als array[index] ist. track ist der größte verbleibende Wert, sodass bei jedem Durchlauf das Maximum vorwärts verschoben wird und das fertige Array von hoch nach niedrig verläuft.

Ja. Eine rekursive Methode findet das Minimum des aktuellen Teilarrays, fügt es an den Anfang des Arrays ein und ruft sich dann selbst für den Rest auf. Die Anzahl der Vergleiche bleibt unverändert, aber der Aufrufstapel benötigt O(n) Speicherplatz, weshalb die Schleifenform vorzuziehen ist.

Häufige Fehler sind das Vergessen, den Index zu Beginn jedes Durchlaufs auf i zurückzusetzen, der Start der inneren Schleife bei i anstatt bei i + 1 und das Vertauschen von Elementen.ping array[j] statt array[index], wodurch verloren geht track mit dem kleinsten Wert.

Nein. `Arrays.sort()` verwendet für primitive Datentypen einen Dual-Pivot-Quicksort und für Objekte TimSort, wobei bei sehr kleinen Partitionen ein Insertion-Style-Sort zum Einsatz kommt. Selection Sort findet sich eher in Lehrmaterialien und handgeschriebenem Code als in der Standardbibliothek.

Fassen Sie diesen Beitrag mit folgenden Worten zusammen: