Auswahl In Java sortieren

1. Einleitung

In diesem Tutorial lernen wir die Auswahlsortierung kennen , sehen uns die Implementierung in Java an und analysieren die Leistung.

2. Algorithmusübersicht

Die Auswahlsortierung beginnt mit dem Element an der 1. Position eines unsortierten Arrays und durchsucht nachfolgende Elemente, um das kleinste Element zu finden . Einmal gefunden, wird das kleinste Element mit dem Element an der 1. Position ausgetauscht.

Der Algorithmus bewegt sich dann zu dem Element an der 2. Position und durchsucht nachfolgende Elemente, um den Index des zweitkleinsten Elements zu finden. Einmal gefunden, wird das zweitkleinste Element mit dem Element an der 2. Position ausgetauscht.

Dieser Prozess wird fortgesetzt, bis wir das n-1-te Element des Arrays erreichen, wodurch das n-1-kleinste Element an die n-1-Position gebracht wird. Das letzte Element wird in der n-1ten Iteration automatisch eingefügt, wodurch das Array sortiert wird.

Wir finden das größte Element anstelle des kleinsten Elements, um das Array in absteigender Reihenfolge zu sortieren.

Sehen wir uns ein Beispiel für ein unsortiertes Array an und sortieren es in aufsteigender Reihenfolge, um den Algorithmus visuell zu verstehen.

2.1. Ein Beispiel

Betrachten Sie das folgende unsortierte Array:

int [] arr = {5, 4, 1, 6, 2}

Iteration 1

In Anbetracht der obigen Funktionsweise des Algorithmus beginnen wir mit dem Element an der 1. Position - 5 - und durchsuchen alle nachfolgenden Elemente, um das kleinste Element - 1 zu finden. Anschließend tauschen wir das kleinste Element mit dem Element an der 1. Position aus.

Das geänderte Array sieht nun wie folgt aus:

{1, 4, 5, 6, 2}

Insgesamt durchgeführte Vergleiche: 4

Iteration 2

In der zweiten Iteration gehen wir zum zweiten Element - 4 - über und durchsuchen nachfolgende Elemente, um das zweitkleinste Element - 2 zu finden. Anschließend tauschen wir das zweitkleinste Element mit dem Element an der 2. Position aus.

Das geänderte Array sieht nun folgendermaßen aus:

{1, 2, 5, 6, 4}

Insgesamt durchgeführte Vergleiche: 3

In ähnlicher Weise haben wir die folgenden Iterationen:

Iteration 3

{1, 2, 4, 6, 5}

Insgesamt durchgeführte Vergleiche: 2

Iteration 4

{1, 2, 4, 5, 6}

Insgesamt durchgeführte Vergleiche: 1

3. Implementierung

Lassen Sie uns die Auswahlsortierung mithilfe einiger for- Schleifen implementieren :

public static void sortAscending(final int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int minElementIndex = i; for (int j = i + 1; j  arr[j]) { minElementIndex = j; } } if (minElementIndex != i) { int temp = arr[i]; arr[i] = arr[minElementIndex]; arr[minElementIndex] = temp; } } }

Um es umzukehren, könnten wir natürlich etwas ganz Ähnliches tun:

public static void sortDescending(final int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int maxElementIndex = i; for (int j = i + 1; j < arr.length; j++) { if (arr[maxElementIndex] < arr[j]) { maxElementIndex = j; } } if (maxElementIndex != i) { int temp = arr[i]; arr[i] = arr[maxElementIndex]; arr[maxElementIndex] = temp; } } }

Und mit etwas mehr Ellbogenfett könnten wir diese mit Komparatoren kombinieren .

4. Leistungsübersicht

4.1. Zeit

In dem Beispiel, das wir zuvor gesehen haben, erforderte die Auswahl des kleinsten Elements insgesamt (n-1) Vergleiche, gefolgt von einem Austausch an die erste Position. In ähnlicher Weise erforderte die Auswahl des nächstkleineren Elements Gesamtvergleiche (n-2), gefolgt von einem Austausch an der 2. Position und so weiter.

Ausgehend von Index 0 führen wir also n-1, n-2, n-3, n-4… aus. 1 Vergleiche. Das letzte Element wird aufgrund früherer Iterationen und Swaps automatisch eingefügt.

Mathematisch sagt uns die Summe der ersten n-1 natürlichen Zahlen , wie viele Vergleiche wir benötigen, um ein Array der Größe n mit Selection Sort zu sortieren .

Die Formel für die Summe von n natürlichen Zahlen lautet n (n + 1) / 2 .

In unserem Fall benötigen wir die Summe der ersten n-1 natürlichen Zahlen. Daher ersetzen wir n durch n-1 in der obigen Formel, um Folgendes zu erhalten:

(n-1) (n-1 + 1) / 2 = (n-1) n / 2 = (n ^ 2-n) / 2

Wenn n ^ 2 prominent wächst, wenn n wächst, betrachten wir die höhere Potenz von n als Leistungsbenchmark, wodurch dieser Algorithmus eine zeitliche Komplexität von O (n ^ 2) aufweist.

4.2. Raum

In Bezug auf die Komplexität des Hilfsraums erfordert die Auswahlsortierung eine zusätzliche Variable, um den Wert vorübergehend für den Austausch zu halten. Daher ist die Raumkomplexität von Selection Sort O (1) .

5. Schlussfolgerung

Selection Sort ist ein sehr einfacher Sortieralgorithmus, der zu verstehen und zu implementieren ist. Leider macht es seine quadratische Zeitkomplexität zu einer teuren Sortiertechnik . Da der Algorithmus jedes Element durchsuchen muss, ist auch die Komplexität der Zeit im besten Fall, im Durchschnittsfall und im schlechtesten Fall gleich .

Andere Sortiertechniken wie Insertion Sort und Shell Sort weisen ebenfalls eine quadratische Worst-Case-Zeitkomplexität auf, weisen jedoch im besten und durchschnittlichen Fall eine bessere Leistung auf.

Schauen Sie sich den vollständigen Code für Selection Sort over auf GitHub an.