Sortieralgorithmen in Java - Verschiedene Arten von Sortieralgorithmen in Java

• Einführung in Sortieralgorithmen in Java

Einführung in Sortieralgorithmen in Java

Um die Informationen in einer bestimmten Reihenfolge zu sortieren, oft in einem Array-ähnlichen Rahmen, müssen sie angeordnet werden. Sie können verschiedene Anforderungen für die Reihenfolge verwenden. Beliebte sind das Sortieren von Zahlen vom kleinsten zum größten oder umgekehrt oder das lexikografische Sortieren von Zeichenfolgen. Wir werden verschiedene Algorithmen behandeln, von ineffektiven, aber intuitiven Alternativen bis hin zu effizienten Algorithmen, die effektiv in Java und in anderen Sprachen implementiert sind, wenn Sie daran interessiert sind, wie das Sortieren funktioniert.

Verschiedene Sortieralgorithmen in Java

Es gibt verschiedene Sortieralgorithmen und nicht alle sind gleich effektiv. Um sie zu vergleichen und festzustellen, welche am besten abschneiden, analysieren wir ihre zeitliche Komplexität.

1. Sortieren durch Einfügen
2. Bubble Sort
3. Auswahl sortieren
4. Zusammenführen, sortieren
5. Heapsort

1. Insertion Sort

Das Konzept hinter Einfügesortierung unterteilt den Bereich in die sortierten und unsortierten Subarrays. Der klassifizierte Teil befindet sich zu Beginn der Dauer 1 und stimmt mit der ersten (linken) Komponente im Array überein. Wir bewegen uns durch das Array und erweitern den klassifizierten Teil des Arrays bei jeder Iteration um eine Komponente. Wenn wir expandieren, positionieren wir das frische Element im sortierten Subarray. Dazu verschieben wir alle Elemente nach rechts, bis wir feststellen, dass wir die erste Komponente nicht mehr ändern müssen. Wenn der fette Teil in aufsteigender Reihenfolge sortiert ist, beispielsweise in dem folgenden Array, tritt dies auf:

1. 3 5 7 8 4 2 1 9 6: Betrachten Sie 4 und fügen Sie dies ein, was wir brauchen. Wir haben seit 8> 4 verschoben
2. 2. 3 5 7 x 8 2 1 9 6
3. 3 5 x 7 8 2 1 9 6
4. 3 x 5 7 8 2 1 9 6
5. 3 4 5 7 8 2 1 9 6

Code:

public class InsertionSortEx (
public static void insertionSort(int() arr) (
for (int x = 1; x < arr.length; x++) (
int current = arr(x);
int y = x - 1;
while(y >= 0 && current < arr(y)) (
arr(y+1) = arr(y);
y--;
)
arr(y+1) = current;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 7, 8, 4, 2, 1, 9, 6);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
insertionSort(arr1);//sorting array using insertion sort
System.out.println("After Insertion Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)

Ausgabe:

Nach dieser Methode wurde der sortierte Teil um eine Komponente erweitert. Wir haben jetzt fünf statt vier Elemente. Dies geschieht bei jeder Iteration, und das gesamte Array wird bis zum Ende sortiert.

Anmerkung: Dies liegt daran, dass wir die gesamte klassifizierte Liste nacheinander in jeder Iteration übertragen müssen. Dies ist O (n). Für jede Komponente in jeder Tabelle müssen wir dies tun, was impliziert, dass sie an O (n 2) gebunden ist.2.

2. Bubble Sort

Befindet sich die Blase nicht in der erforderlichen Reihenfolge, werden benachbarte Komponenten ausgetauscht. Dies wird wiederholt, bis alle Komponenten ab dem Start des Arrays in Ordnung sind. Wir wissen, dass, wenn es uns gelingt, die gesamte Iteration ohne Austausch durchzuführen, alle Elemente im Vergleich zu den angrenzenden Elementen in der gewünschten Reihenfolge und damit auch das gesamte Array vorliegen. Der Grund für den Bubble-Sort-Algorithmus ist, dass die Zahlen wie „sprudeln“ in den „Boden“. Wenn Sie nach einer bestimmten Anzahl die Instanz erneut durchlaufen (4 ist eine gute Instanz), werden Sie feststellen, dass die Zahl langsam ist bewegt sich nach rechts.

Die Schritte zur Blasensortierung lauten wie folgt:

1. 4 2 1 5 3: Hier sind die ersten beiden Zahlen nicht in der richtigen Reihenfolge, daher müssen wir beide Zahlen sortieren.
2. 2 4 1 5 3: Danach ist auch das nächste Zahlenpaar nicht in der richtigen Reihenfolge. Es wird also erneut sortiert.
3. 2 1 4 5 3: Diese beiden sind in der richtigen Reihenfolge, 4 <5, daher müssen sie nicht ausgetauscht werden.
4. 2 1 4 5 3 : Wieder müssen wir für die richtige Reihenfolge tauschen.
5. 2 1 4 3 5: Hier ist das resultierende Array nach einer Iteration.
6. Wir müssen diesen Vorgang wiederholen, bis die Zahlen in der richtigen Reihenfolge sind.

Code:

public class BubbleSortExample (
public static void bubbleSort(int() arr) (
int n = arr.length;
int tmp = 0;
for(int x=0; x < n; x++)(
for(int y=1; y < (nx); y++)(
if(arr(y-1) > arr(y))(
//swap elements
tmp = arr(y-1);
arr(y-1) = arr(y);
arr(y) = tmp;
)
)
)
)
public static void main(String() args) (
int arr() =(4, 2, 1, 5, 3);
System.out.println("Array Before Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
System.out.println();
bubbleSort(arr);
System.out.println("Array After Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
)
)

Ausgabe:

Hinweis: Wenn ich a (i)> = a (i + 1) verwendet hätte, wäre es möglicherweise zu einer Endlosschleife gekommen, da diese Verbindung mit äquivalenten Komponenten immer noch gültig wäre und diese daher immer von einem Element zum anderen vertauscht würden.

3. Auswahl sortieren

Auswahlsortierung teilt das Array in ein Array von Klassifizierungen auf, die nicht sortiert sind. Dieses Mal wird das sortierende Subarray jedoch gebildet, indem am Ende des sortierten Arrays das minimale Element des unsortierten Subarrays eingefügt wird, indem Folgendes ausgetauscht wird:

1. 3 5 1 2 4
2. 1 5 3 2 4
3. 1 2 3 5 4
4. 1 2 3 5 4
5. 1 2 3 4 5
6. 1 2 3 4 5

Code:

public class SelectionSortEx (
public static void selectionSort(int() arr)(
for (int x = 0; x < arr.length - 1; x++)
(
int indx = x;
for (int y = x + 1; y < arr.length; y++)(
if (arr(y) < arr(indx))(
indx = y;
)
)
int smallNumber = arr(indx);
arr(indx) = arr(x);
arr(x) = smallNumber;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 1, 2, 4);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
selectionSort(arr1);
System.out.println("After Selection Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)

Ausgabe:

Hinweis: Das Minimum ist O (n) für die Arraygröße, da alle Komponenten überprüft werden müssen. Für jedes Element des Arrays müssen wir das Minimum finden und den gesamten Prozess O (n 2) einschränken.

4. Sortieren zusammenführen

Beim Sortieren zusammenführen wird eine Rekursion verwendet, um das Problem der Divisions- und Eroberungsmethode wirksamer als bei zuvor beschriebenen Algorithmen zu beheben.

Dieser Baum zeigt, wie die rekursiven Aufrufe funktionieren. Mit Pfeil nach unten markierte Arrays sind die Arrays, für die wir die Funktion aufrufen, während wir Pfeil-Arrays zusammenfassen. Dann folgen Sie dem Pfeil zum Rand des Baumes und kehren dann zurück und verschmelzen. Wir haben 3 5 3 1 Reichweite, also teilen wir sie in 3 5 4 und 2 1 auf. Wir teilen sie in ihre Teile auf, um sie zu sortieren. Wir fangen an, sie zu fusionieren und zu sortieren, wenn wir auf den Grund gehen.

Code:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class MergeSort (
static void merge(int() array, int lowval, int midval, int highval)(
int x, y, k;
int() c= new int(highval-lowval+1);
k = 0;
x=lowval;
y=midval+1;
while(x<=midval && y<=highval)(
if(array(x)<=array(y))(
c(k++) = array(x++);
)
else(
c(k++) = array(y++);
)
)
while(x<=midval)(
c(k++) = array(x++);
)
while(y<=highval)(
c(k++) = array(y++);
)
k=0;
for(x = lowval; x<=highval; x++)(
array(x) = c(k++);
)
)
static void mergeSort(int() array, int lowval, int highval)(
if(highval-lowval+1>1)(
int midval = (lowval+highval)/2;
mergeSort(array, lowval, midval);
mergeSort(array, midval+1, highval);
merge(array, lowval, midval, highval);
)
)
public static void main(String() args) (
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
int size;
System.out.println("Enter the array");
try (
size = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("Please Enter valid Input");
return;
)
int() array = new int(size);
System.out.println("Enter array elements");
int x;
for (x = 0; x < array.length; x++) (
try (
array(x) = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("An error Occurred");
)
)
System.out.println("After Sorting");
System.out.println(Arrays.toString(array));
mergeSort(array, 0, array.length-1);
System.out.println("Before Merge Sorting");
System.out.println(Arrays.toString(array));
)
)

In diesem Programm haben wir den Benutzer aufgefordert, Eingaben zu machen. Die Ausgabe erfolgt in sortierter Reihenfolge basierend auf der Benutzereingabe.

Ausgabe:

5. Heap-Sortierung

Sie müssen zuerst das Framework kennen, auf dem Heapsort ausgeführt wird - den Heap, um zu verstehen, warum er ausgeführt wird. Wir werden speziell über einen binären Heap sprechen, aber Sie können dies auch auf andere Heap-Konstruktionen verallgemeinern. Ein Haufen ist ein Baum, der die Eigenschaft des Haufens erfüllt, dass alle seine untergeordneten Elemente Beziehungen zu jedem Knoten haben. Ein Haufen muss auch fast fertig sein. Eine nahezu vollständige d-depth-Binärdatei hat einen d-1-Teilbaum mit derselben Wurzel, und jeder Knoten hat einen vollständigen linken Teilbaum mit einem nach links absteigenden Teilbaum.

Mit anderen Worten, Sie erhalten eine niedrigere und niedrigere Zahl (Min-Heap) oder eine größere und größere Zahl (Max-Heap), wenn Sie sich auf dem Baum nach unten bewegen. Hier ist eine Max-Heap-Instanz:

1. 6 1 8 3 5 2 4 : Hier sind beide Kinderzahlen kleiner als die Eltern, daher müssen wir nichts ändern.
2. 6 1 8 3 5 2 4: Hier, 5> 1, müssen wir sie tauschen. Wir müssen uns für 5 häufen.
3. 6 5 8 3 1 2 4: Beide Kinderzahlen sind kleiner, alles bleibt gleich.
4. 6 5 8 3 1 2 4: Hier 8> 6, daher sollten wir sie tauschen.
5. 8 5 6 3 1 2 4: Nach dieser Iteration erhalten wir dieses Ergebnis.

Nach nochmaliger Wiederholung dieses Vorgangs erhalten wir folgende Ergebnisse:

• 8 5 6 3 1 2 4

1. 4 5 6 3 1 2 8 : Tauschen
2. 6 5 4 3 1 2 8 : Häufen
3. 2 5 4 3 1 6 8 : Tauschen
4. 5 2 4 2 1 6 8 : Häufen
5. 1 2 4 2 5 6 8 : Tauschen

Code:

public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
) public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
)

Ausgabe:

Sie können es von Punkt zu Ebene des Diagramms von links nach rechts anzeigen. Was wir hier erreicht haben, ist, dass wenn wir die k-te Komponente im Array haben, die Position ihrer Kinder 2 \ * k + 1 und 2 \ * k + 2 ist (vorausgesetzt, die Indizierung beginnt bei 0). Dies kann von Ihnen überwacht werden. Die Position des Elternteils ist immer (k-1) / 2 für die k-te Komponente. Sie können jeden Bereich problemlos "aufhäufen", weil Sie das wissen. Überprüfen Sie, ob eines der Kinder für jede Komponente niedriger ist. Wenn ja, koppeln Sie ein übergeordnetes Element und wiederholen Sie diesen Schritt rekursiv mit dem übergeordneten Element.

Hinweis: Da die Iteration von for-Schleifen über das gesamte Array hinweg zu heapSort führt (offensichtlich O (N)), würde dies die Gesamtkomplexität von Heapsort O erzeugen (nlog n). 1) mehr Platz als Merge Sort, aber es hat einige Nachteile, wie zum Beispiel harte Parallelen.

Fazit - Sortieralgorithmen in Java

Das Sortieren ist bei Datensätzen weit verbreitet, sei es zur weiteren Analyse oder zur Beschleunigung der Suche mit effektiveren Algorithmen, die auf sortierten Informationen, Filterinformationen usw. beruhen. Das Sortieren wird von mehreren Sprachen unterstützt, und häufig verdecken die Schnittstellen die Aufgaben des Programmierers.

Empfohlene Artikel

Dies ist eine Anleitung zum Sortieren von Algorithmen in Java. Hier diskutieren wir verschiedene Sortierungsarten in Java mit ihren Algorithmen. Sie können auch unsere anderen Artikelvorschläge durchgehen -

1. Sortieralgorithmen in Java zusammenführen
2. JComboBox in Java
3. StringBuffer in Java
4. JTextField in Java
5. Heap-Sortierung in Python
6. Schnelle Sortieralgorithmen in Java
7. Komplette Anleitung zum Sortieren in C # mit Beispielen
8. Sortieralgorithmen in JavaScript
9. Leitfaden zu Beispielen für C ++ - Algorithmen
10. Komplette Anleitung zum Sortieren von Algorithmen in Python