Auswahl Sortierung in Java Programm mit Beispiel
James Hartmann
โก 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.
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.
