Einführung in Merge-Sortieralgorithmen in Java
Merge-Sorting-Algorithmen sind in der Informatik sehr wichtig. Die Ausgabe der Sortierung besteht darin, die Elemente einer Liste in einer bestimmten Reihenfolge anzuordnen (entweder aufsteigend oder absteigend). Merge Sort ist einer der effizientesten verfügbaren Sortieralgorithmen, da er auf dem Konzept von Divide und Conquers basiert. Teilen Sie, wie der Name schon sagt, zunächst das größere Problem in kleine Probleme auf, bevor Sie die kleineren Probleme lösen, um das größere Problem zu lösen. In diesem Artikel werden wir Merge-Sortieralgorithmen in Java behandeln. Konzeptionell ist Merge Sort eine Kombination aus zwei grundlegenden Algorithmen namens MERGE und MERGE_SORT, die wie folgt funktionieren:
- Teilen Sie die unsortierte Liste in n Unterlisten mit einzelnen Elementen auf (n ist die Gesamtzahl der Elemente in der unsortierten Liste).
- Führe Unterlisten wiederholt zu sortierten Unterlisten zusammen, bis es nur noch eine sortierte Liste gibt.
Implementierung von Merge Sorting Algorithmen in Java
Der MERGE-Algorithmus kombiniert zwei sortierte Listen zu einer sortierten Liste.
Beispiel: Angenommen, es gibt zwei Listen, dh Liste 1 (6, 3) und Liste 2 (3, 1, 9).
1. Sortieren Sie zuerst beide Listen.
Liste 1
Liste 2
Jetzt wenden wir eine Mischtechnik darauf an.
- Dann erstellen wir eine neue Liste der Größe m + n, wobei m die Anzahl der Elemente in Liste 1 und n die Anzahl der Elemente in Liste 2 ist.
Liste 3
In unserem Fall ist m = 2 und n = 3, also ist m + n = 5.
- Jetzt haben wir zwei Zeiger. Ein erster Zeiger, der auf die erste Position von Liste 1 zeigt, und ein zweiter Zeiger, der auf die erste Position von Liste 2 zeigt.
4. Dann vergleichen wir den Wert beider Zeiger. Kopieren Sie den Zeiger mit einem niedrigeren Wert in Liste 3 und bewegen Sie den Zeiger rechts neben die Liste mit dem niedrigeren Wert und der resultierenden Liste (dh Liste 1 und Liste 3).
5. Führen Sie Schritt 4 auf ähnliche Weise immer wieder aus.
Weiterfahrt… ..
HINWEIS: Wenn eine der Listen (dh Liste 1 oder Liste 2) wie oben beschrieben vollständig durchlaufen wird, kopieren Sie den gesamten Inhalt der anderen Listen wie folgt vom Zeiger in die Ergebnisliste (dh Liste 3).
Algorithmus & Pseudocode
Die beiden im Merge-Algorithmus verwendeten Algorithmen sind:
- Das MERGE (ARR, F, M, L) ist ein Prozess, der Folgendes voraussetzt:
- ARR (F… .M) und ARR (M + 1… .L) sind sortierte Listen.
- Führt die beiden sortierten Unterlisten zu einem ARR (F… .L) zusammen.
- SORT (ARR (), F, L) // hier ist F der erste und L der letzte Index des Arrays.
Wenn (L> 1)
- Suchen Sie den Mittelpunkt, um die Liste in zwei Hälften zu teilen:
mittleres M = (F + L) / 2
- Merge Sort für die erste Hälfte aufrufen:
SORT anrufen (ARR, 1, M)
- Rufen Sie Merge Sort für die zweite Hälfte auf:
SORT aufrufen (ARR, M + 1, L)
- Füge die in Schritt 2 und 3 sortierten Hälften zusammen:
MERGE aufrufen (ARR, L, M, R)
Beispiel
Nehmen wir ein Beispiel für ein Array ARR (10, 6, 8, 5, 7, 3, 4). Wir werden den Merge-Algorithmus verwenden, um das Array mithilfe seiner Divide- und Conquer-Technik zu sortieren. Die folgende Abbildung zeigt, dass das Array rekursiv in zwei Hälften geteilt wird, bis die Größe 1 wird. Sobald die Größe 1 wird, rufen wir Zusammenführungsprozesse auf und beginnen, Listen wieder zusammenzuführen, bis die vollständige Liste zusammengeführt ist.
ANMERKUNG: In der folgenden Abbildung geben die roten Zahlen die Reihenfolge an, in der die Schritte verarbeitet werden, um das sortierte Array zu bilden.
Programmcode:
import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)
Ausgabe:
Fazit - Sortieralgorithmen in Java zusammenführen
Die besten, schlechtesten und durchschnittlichen Zeitkomplexitäten der Zusammenführungssortierung sind gleich, wodurch der Algorithmus effizienter wird. Es funktioniert schneller als andere Sortiertechniken. Die Zusammenführungssortierung kann auf Dateien beliebiger Größe angewendet werden. Es ist aufgrund der Verwendung der Divide-and-Conquer-Methode in hohem Maße parallelisierbar. Um fundierte Grundlagen in der Informatik zu entwickeln, sollten Sie die verschiedenen Sortieralgorithmen gründlich verstehen.
Empfohlene Artikel
Dies ist eine Anleitung zum Zusammenführen von Sortieralgorithmen in Java. Hier diskutieren wir die Implementierung von Merge Sorting Algorithmen in Java und Algorithm & Pseudocode mit Beispiel. Sie können auch unsere anderen Artikelvorschläge durchgehen -
- Auswahl Sortieren in Java
- Case Statement in Java
- Zugriffsmodifikatoren in Java
- Sortieren in JavaScript zusammenführen
- Was ist Case Statement in JavaScript?
- Zugriffsmodifikatoren in PHP
- Schnelle Sortieralgorithmen in Java
- Komplette Anleitung zum Sortieren in C # mit Beispielen
- Sortierfunktion in Python mit Beispielen
- Top 6 Sortieralgorithmus in JavaScript