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. 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 dir die Auswahl zu erleichtern, werden wir in unserer Serie die bekanntesten Datensortieralgorithmen nacheinander vorstellen, ihre Prinzipien, Vor- und Nachteile erklären und sie in Java programmieren. Bislang haben wir die folgenden Sortieralgorithmen behandelt:

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

1. Zu Beginn des Algorithmus gehen wir davon aus, dass das erste Element (des unsortierten Teils) das Minimum (d. h. das kleinste) ist.
2. Wir vergleichen dieses Element mit den übrigen Elementen im unsortierten Teil des Arrays und suchen nach dem wirklich kleinsten Element.
3. Wenn wir ein unbedeutendes Element im unsortierten Teil gefunden haben, ersetzen wir die Elemente.
4. Das ersetzte Element wird Teil des sortierten Datensatzes, sein Index wird um 1 erhöht und der unsortierte Teil wird verringert.
5. 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

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 dort 8 verschiedene Arten von Algorithmen, und die Animation kann auch rückwärts abgespielt werden. 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.

Über den Autor

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.