Schnellster Sortieralgorithmus Java
Dieser Artikel behandelt die zwei schnellsten Sortieralgorithmen und schreibt ihren Code in Java.
Die erste Technik ist das Zählende Sortieren, das einige Einschränkungen hat. Daher werden wir auch den Merge-Sort-Algorithmus behandeln.
Zählender Sortieralgorithmus in Java
Der zählende Sortieralgorithmus ist eine der schnellsten Sortiertechniken, die wir verwenden können, wenn Array-Elemente innerhalb eines bestimmten Bereichs angegeben werden. Es ist keine vergleichsbasierte Sortiertechnik, aber es sortiert das Array, indem es die Häufigkeit jedes Array-Elements zählt und speichert.
In einfachen Worten, es verwendet Hashing, um das Array zu sortieren.
Benutzer sollten den folgenden Algorithmus für die Zählsortierung befolgen.
-
Finden Sie die maximalen und minimalen Elemente des Arrays.
-
Als nächstes finden Sie den Bereich des Arrays, indem Sie die maximalen und minimalen Elemente verwenden, und erstellen Sie ein neues
freq-Array mit Größenbereich, um die Frequenz jedes Elements zu speichern. -
Durchlaufen Sie das ursprüngliche Array und speichern Sie die Frequenz jedes Elements im Array
freq. -
Zählen Sie die kumulativen Häufigkeiten für jedes Element, indem Sie die Häufigkeiten addieren.
-
Beginnen Sie am Ende mit der Iteration zum ursprünglichen Array und bringen Sie jedes Element mit dem Array
freqan seine sortierte Position. -
Speichern Sie alle sortierten Elemente von
Ergebnisim ursprünglichen Array, um das ursprüngliche Array sortiert zu machen.
Beispielcode:
class CountingSort {
// function to find the maximum from the array
static int findMax(int arr[]) {
int maxi = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > maxi)
maxi = arr[i];
}
return maxi; // return maximum
}
// function to find the minimum from the array
static int findMin(int arr[]) {
int mini = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < mini)
mini = arr[i];
}
return mini; // return minimum
}
static void cntSort(int[] arr) {
int maxi = findMax(arr);
int mini = findMin(arr);
// getting range from maximum and minimum elements of the array
int range = maxi - mini + 1;
// creating the array to store the frequency of elements
int freq[] = new int[range];
// resultant array
int result[] = new int[arr.length];
// counting frequency of elements and storing it to freq array
for (int i = 0; i < arr.length; i++) {
freq[arr[i] - mini]++;
}
// Doing addition of frequency
for (int i = 1; i < freq.length; i++) {
freq[i] += freq[i - 1];
}
// Putting every element of arr to its correct place based on the freq array
for (int i = arr.length - 1; i >= 0; i--) {
result[freq[arr[i] - mini] - 1] = arr[i];
freq[arr[i] - mini]--;
}
// Make arr array sorted by assigning elements from the result array
for (int i = 0; i < arr.length; i++) {
arr[i] = result[i];
}
}
public static void main(String[] args) {
int[] arr = {10, 20, -2, -4, 3, 40, 50, 30, 20, 10};
cntSort(arr);
System.out.println("Sorted Array using counting sort is ");
for (int a = 0; a < arr.length; a++) {
System.out.print(arr[a] + " ");
}
}
}
Ausgang:
Sorted Array is -4 -2 3 10 10 20 20 30 40 50
Zeitkomplexität des zählenden Sortieralgorithmus in Java
Die Zeitkomplexität für Counting Sort ist linear, da wir eine einzelne for-Schleife verwenden.
| I’m besten fall | O(n+k) |
| Durchschnittlicher Fall | O(n+k) |
| Schlimmsten Fall | O(n+k) |
Raumkomplexität des zählenden Sortieralgorithmus in Java
Die Raumkomplexität für die zählende Sortierung ist O(n), da wir das temporäre Array verwenden, um sortierte Elemente zu speichern.
Einschränkungen des zählenden Sortieralgorithmus in Java
Die zählende Sortiertechnik ist ohne Zweifel der schnellste Algorithmus zum Sortieren von Elementen des Arrays, hat jedoch einige Einschränkungen.
Benutzer können sich ein Szenario vorstellen, in dem die Array-Länge sehr klein und der Eingabebereich zu groß ist, z. B. Millionen. Auch der Bubble Sort kann in solchen Fällen besser abschneiden.
Benutzer können es also verwenden, um das Array in linearer Zeit zu sortieren, wenn der Eingabebereich klein ist.
Zusammenführungssortieralgorithmus in Java
Um die Einschränkungen des Zählsortierens zu überwinden, können Benutzer die Merge-Sort-Technik verwenden.
Der Merge-Sort-Algorithmus folgt dem Divide-and-Conquer-Ansatz. Zuerst teilt es das Array in zwei Hälften, sortiert es und führt das sortierte Array zusammen.
Um den vollständigen Algorithmus Schritt für Schritt zu lernen, können Benutzer die folgenden Schritte ausführen.
-
Finden Sie den Mittelpunkt des Arrays.
-
Rufen Sie rekursiv die Funktion
mergeSort()für den ersten und zweiten Teil des Arrays auf. -
Rufen Sie die Funktion
merge()auf, um das Array zusammenzuführen. -
Erstellen Sie in der Funktion
merge()zwei temporäre Arrays mit der gleichen Größe wie zwei Teile des Arrays und speichern Sie das Array-Element im entsprechenden temporären Array. -
Iterieren Sie durch die temporären Arrays, bis beide unsortierte Elemente haben, finden Sie das kleinste Element aus beiden Arrays, speichern Sie es im ursprünglichen Array und bewegen Sie sich weiter.
-
Wenn ein Element im
LeftArrayverbleibt, speichern Sie es im ursprünglichen Array und machen Sie dasselbe für dasRightArray.
Beispielcode:
class Test {
// function to merge two sorted arrays
static void merge(int arr[], int left, int mid, int right) {
// sizes for temp arrays
int n1 = mid - left + 1;
int n2 = right - mid;
// temp arrays
int LeftArray[] = new int[n1];
int RigthArray[] = new int[n2];
// clone data to temp arrays
for (int i = 0; i < n1; ++i) LeftArray[i] = arr[left + i];
for (int j = 0; j < n2; ++j) RigthArray[j] = arr[mid + 1 + j];
int a = 0, b = 0;
// merging temp arrays to the original array
int k = left;
while (a < n1 && b < n2) {
if (LeftArray[a] <= RigthArray[b]) {
arr[k] = LeftArray[a];
a++;
} else {
arr[k] = RigthArray[b];
b++;
}
k++;
}
// If any elements are left in LeftArray, clone it to the original array
while (a < n1) {
arr[k] = LeftArray[a];
a++;
k++;
}
// If any elements are left in RightArray, clone it to the original array
while (b < n2) {
arr[k] = RigthArray[b];
b++;
k++;
}
}
static void mergeSort(int arr[], int left, int right) {
if (left < right) {
// Find the mid of the array using the left and right
int mid = left + (right - left) / 2;
// sort the first half of the array
mergeSort(arr, left, mid);
// sort the second half of the array
mergeSort(arr, mid + 1, right);
// sort both parts of the array and merge it
merge(arr, left, mid, right);
}
}
public static void main(String args[]) {
int[] arr = {10, 201, -22121, -412, 3, 212121, 50, 30, 20, 1021212};
mergeSort(arr, 0, arr.length - 1);
System.out.println("Sorted array using merge sort is");
for (int a = 0; a < arr.length; a++) {
System.out.print(arr[a] + " ");
}
}
}
Ausgang:
Sorted array is -22121 -412 3 10 20 30 50 201 212121 1021212
Zeitkomplexität des Merge-Sort-Algorithmus in Java
Die Zeitkomplexität für mergeSort() ist O(nlogn), wobei n die Länge des Arrays ist. Hier ist die Zeitkomplexität der Funktion merge() O(n) und die Zeitkomplexität der Funktion mergeSort() ist O(logn), da wir für every einen rekursiven Aufruf machen halber Teil des Arrays.
| I’m besten fall | O(nlog(n)) |
| Durchschnittlicher Fall | O(nlog(n)) |
| Schlimmsten Fall | O(nlog(n)) |
Raumkomplexität des Merge-Sort-Algorithmus in Java
Die Raumkomplexität für die Zusammenführungssortierung beträgt O(n), da wir die beiden temporären Arrays verwenden, um unsortierte Elemente zu speichern.
In diesem Artikel haben wir Schritt für Schritt den Counting-Sort-Algorithmus, einen der schnellsten Algorithmen in Java, anhand seines Beispielcodes kennengelernt. Um die Einschränkungen der Zählsortierung zu überwinden, haben wir außerdem die Zusammenführungssortierung gelernt, die für jeden Eingabebereich funktioniert.
