Java Entwickler Experte
Selection sort – Sortieren nach Auswahl in Java
Sortieralgorithmen werden verwendet, um die Elemente eines Arrays oder einer Liste in aufsteigender oder absteigender numerischer oder lexikografischer Reihenfolge neu zu ordnen. Die Sortierung ist sehr wichtig für die optimale Leistung anderer Algorithmen, die sortierte Eingabedaten benötigen.
In diesem Artikel erfährst du:
Es gibt eine Reihe von verschiedenen Sortieralgorithmen. Die Auswahl eines geeigneten Algorithmus hängt von Faktoren wie der Größe und den Eigenschaften der Eingabedaten, dem verfügbaren Speicher und den Zeit- und Platzanforderungen ab.
Um Ihnen die Auswahl zu erleichtern, stellen wir Ihnen in unserer Serie die bekanntesten Datensortieralgorithmen vor, erklären ihre Prinzipien, Vor- und Nachteile und programmieren sie in Java.
Bislang haben wir die folgenden Sortieralgorithmen besprochen:
- Sortieralgorithmen: eine Einführung in das Sortieren von Daten,
- Bubble sort – Blasen-Sortierung,
- Comb sort – Kamm-Sortierung,
- Big O Notation: Analyse der Algorithmenkomplexität.
Heute werden wir uns Selection soft (die Auswahlsortierung) ansehen.
Selection sort Algoritmus
Sortieren durch Auswahl ist ein einfacher Datensortieralgorithmus, der das Eingabefeld in zwei Teile unterteilt: sortiert und unsortiert. Er wählt dann wiederholt das kleinste (größte) Element aus dem unsortierten Teil aus und verschiebt es in den sortierten Teil. Der Algorithmus ist bei einer großen Anzahl von Elementen in der Eingabe sehr ineffizient. Er wird jedoch häufig in Situationen verwendet, in denen die Eingabe relativ wenige Elemente enthält, meist in Kombination mit anderen Sortieralgorithmen.
Das Funktionsprinzip des Selection Sort Algorithmus
Nehmen wir an, wir wollen den Eingabevektor vom kleinsten zum größten Element sortieren. Bei der umgekehrten Sortierung wird die gesamte Logik des Algorithmus invertiert. Der sortierte Teil des Arrays ist zu Beginn des Algorithmus immer leer.
- Zu Beginn des Algorithmus gehen wir davon aus, dass das erste Element (des unsortierten Teils) das Minimum (d. h. das kleinste) ist.
- Wir vergleichen dieses Element mit den übrigen Elementen im unsortierten Teil des Arrays und suchen nach dem wirklich kleinsten Element.
- Wenn wir ein unbedeutendes Element im unsortierten Teil gefunden haben, ersetzen wir die Elemente.
- Das ersetzte Element wird Teil des sortierten Datensatzes, sein Index wird um 1 erhöht und der unsortierte Teil wird verringert.
- Wir wiederholen die Schritte 1 bis 4, bis das gesamte Array sortiert ist.
Anschließend werden wir ein praktisches Beispiel in Java-Code zeigen.
Vorteile des Algorithmus Selection sort
- Es ist leicht zu verstehen und umzusetzen,
- funktioniert gut für kleine Listen von Daten.
Nachteile des Algorithmus Selection sort
- Die Zeitkomplexität ist O(n²), was ihn zu einem langsamen Algorithmus für einen großen Datensatz macht,
- ist nicht stabil.
Selection Sort – zeitliche Komplexität
| Algorithmus | Methode | Zeitliche Komplexität | Speicher | Stabil | ||
| schlechteste | durchschnittlich | beste | ||||
| Selection sort | Auswahl | O(n²) | O(n²) | O(n²) | O(1) | Nein |
Selection sort, Animation, Visualisierung, gif
Die Visualisierung des Selection sort Algorithmus sieht wie folgt aus:
Quelle: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms
Eine Animation des Algorithmus findest du zum Beispiel unter Toptal. Es gibt 8 Arten von Algorithmen, Sie können die Animation auch rückwärts abspielen.
Auf dieser Seite kannst du die einzelnen Schritte des Algorithmus durchgehen, wodurch du die Zeitkomplexität des Algorithmus überprüfen kannst.
Implementierung von Selection Sort – Java-Programm
Nachdem wir uns mit den Prinzipien des Algorithmus vertraut gemacht haben, können wir ihn nun in Java programmieren.
SelectionSort.java
package sorting;
public class SelectionSort {
private boolean change;
private int temp;
public void sort(int data[])
{
for (int i = 0; i < data.length - 1; i++) {
System.out.println(i + 1 + ". iteration");
// Find the index of the minimum in unsorted part of array
int minIndex = i;
for (int j = i + 1; j < data.length; j++) {
if (data[j] < data[minIndex])
minIndex = j;
}
// Swap the minimum element with first element from unsorted part, unless they are the same
if(i != minIndex) {
System.out.print("Found minimum: " + data[minIndex] + ", swapping with " + data[i] + " => ");
temp = data[minIndex];
data[minIndex] = data[i];
data[i] = temp;
}
else
System.out.print("Minimum: " + data[minIndex] + " is on the right spot, no swapping => ");
printArray(data);
}
}
// Function to print an array
public void printArray(int data[])
{
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
System.out.println();
}
}
Main.java
import sorting.SelectionSort;
public class Main {
public static void main(String[] args) {
int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
SelectionSort selectionSort = new SelectionSort();
System.out.print("Input: ");
selectionSort.printArray(dataToSort);
selectionSort.sort(dataToSort);
System.out.print("Sorted: ");
selectionSort.printArray(dataToSort);
}
}Die Ausgabe dieses Beispiels ist:
Wir haben die Dateien mit dem obigen Beispiel in Form von Code vorbereitet, den du direkt in Java ausführen kannst. Lade den Selection Sort Java-Code hier herunter
Wenn du ein Java Programmierer bist und nach Arbeit suchst, schau dir unsere Mitareiterbenefits an und reagiere auf die neuesten Stellenangebote.
