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