Mergesort-Algorithmus - Implementierung in Java, C und Python
Der Merge-Sort-Algorithmus ist einer der effizientesten Sortieralgorithmen. Er basiert auf dem Prinzip des Teile und Herrsche, das die Idee verfolgt, eine Liste in mehrere Unterlisten zu zerlegen, bis jede Unterliste aus einem einzigen Element besteht, und diese Unterlisten so zu kombinieren, dass eine sortierte Liste entsteht.
Funktionsregel des Mergesort
Das Konzept von Teilen und Herrschen umfasst drei Schritte:
- Teile das Problem in mehrere Teilprobleme auf.
- Lösen Sie die Teilprobleme. Die Idee ist, das Problem in atomare Teilprobleme zu zerlegen, die tatsächlich gelöst werden.
- Kombinieren Sie die Lösungen der Teilprobleme, um die Lösung des eigentlichen Problems zu finden.
Die Arbeitsregel des Merge-Sort-Algorithmus umfasst folgende Schritte:
- Teilen Sie das unsortierte Array in Teilarrays auf, wobei jedes Teilarray ein einzelnes Element enthält.
- Nehmen Sie benachbarte Paare aus zwei eindimensionalen Arrays und fügen Sie sie zusammen, um ein Array mit 2 Elementen zu bilden.
- Wiederholen Sie den Prozess, bis ein einzelnes sortiertes Array erhalten ist.
Ein Array der Größe 'N' wird in zwei Teile der Größe 'N/2' unterteilt. Diese Arrays werden dann weiter unterteilt, bis wir ein einzelnes Element erreichen. Der Basisfall besteht darin, ein einzelnes Element zu erreichen. Wenn der Basisfall erreicht ist, beginnen wir, den linken Teil und den rechten Teil zusammenzuführen, und am Ende erhalten wir ein sortiertes Array. Der Merge-Sort-Algorithmus zerlegt wiederholt ein Array in mehrere Teilarrays, bis jedes Teilarray aus einem einzelnen Element besteht, und fügt diese Teilarrays so zusammen, dass ein sortiertes Array entsteht.
Mergesort-Algorithmus-Flow
Array={70,50,30,10,20,40,60}
Wir zerlegen das Array wiederholt in zwei Teile, den linken Teil und den rechten Teil. Die Teilung erfolgt vom mittleren Element aus. Wir teilen, bis wir ein einzelnes Element erreicht haben, und dann beginnen wir, sie zu kombinieren, um ein sortiertes Array zu bilden.
Mergesort-Implementierungen
Wir werden den Mergesort-Algorithmus in Java, C und Python implementieren.
1. Java-Implementierung
package com.journaldev.ds;
public class MergeSort {
public static void main(String[] args) {
int[] arr = { 70, 50, 30, 10, 20, 40, 60 };
int[] merged = mergeSort(arr, 0, arr.length - 1);
for (int val : merged) {
System.out.print(val + " ");
}
}
public static int[] mergeTwoSortedArrays(int[] one, int[] two) {
int[] sorted = new int[one.length + two.length];
int i = 0;
int j = 0;
int k = 0;
while (i < one.length && j < two.length) {
if (one[i] < two[j]) {
sorted[k] = one[i];
k++;
i++;
} else {
sorted[k] = two[j];
k++;
j++;
}
}
if (i == one.length) {
while (j < two.length) {
sorted[k] = two[j];
k++;
j++;
}
}
if (j == two.length) {
while (i < one.length) {
sorted[k] = one[i];
k++;
i++;
}
}
return sorted;
}
public static int[] mergeSort(int[] arr, int lo, int hi) {
if (lo == hi) {
int[] br = new int[1];
br[0] = arr[lo];
return br;
}
int mid = (lo + hi) / 2;
int[] fh = mergeSort(arr, lo, mid);
int[] sh = mergeSort(arr, mid + 1, hi);
int[] merged = mergeTwoSortedArrays(fh, sh);
return merged;
}
}
Ausgabe
2. C Implementierung
#include <stdio.h>
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is the right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
/* Driver program to test above functions */
int main()
{
int arr[] = {70, 50, 30, 10, 20, 40,60};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}
Ausgabe
3. Python-Implementierung
def merge_sort(unsorted_array):
if len(unsorted_array) > 1:
mid = len(unsorted_array) // 2 # Finding the mid of the array
left = unsorted_array[:mid] # Dividing the array elements
right = unsorted_array[mid:] # into 2 halves
merge_sort(left)
merge_sort(right)
i = j = k = 0
# data to temp arrays L[] and R[]
while i < len(left) and j < len(right):
if left[i] < right[j]:
unsorted_array[k] = left[i]
i += 1
else:
unsorted_array[k] = right[j]
j += 1
k += 1
# Checking if any element was left
while i < len(left):
unsorted_array[k] = left[i]
i += 1
k += 1
while j < len(right):
unsorted_array[k] = right[j]
j += 1
k += 1
Code to print the list
def print_list(array1):
for i in range(len(array1)):
print(array1[i], end=" ")
print()
driver code to test the above code
if __name__ == '__main__':
array = [12, 11, 13, 5, 6, 7]
print("Given array is", end="\n")
print_list(array)
merge_sort(array)
print("Sorted array is: ", end="\n")
print_list(array)
Ausgabe
Zeit- und Raumkomplexität des Mergesort-Algorithmus
1. Speicherkomplexität
Hilfsraum: O(n) Sortierung im Platz: Kein Algorithmus: Teile und herrsche
2. Zeitkomplexität
Merge-Sort ist ein rekursiver Algorithmus und die Zeitkomplexität kann durch die folgende Rekursionsbeziehung ausgedrückt werden. T(n)=2T(n/2) + O(n) Die Lösung der obigen Rekursion ist O(nLogn). Die Liste der Größe N wird in maximal Logn Teile unterteilt, und das Zusammenführen aller Teil-Listen zu einer einzigen Liste dauert O(N) Zeit. Die schlechteste Laufzeit dieses Algorithmus ist O(nLogn). Beste Fall Zeitkomplexität: O(n*log n) Schlechteste Fall Zeitkomplexität: O(n*log n) Durchschnittliche Zeitkomplexität: O(n*log n) Die Zeitkomplexität von MergeSort beträgt in allen 3 Fällen (schlecht, durchschnittlich und gut) O(n*Log n), da der Mergesort das Array immer in zwei Hälften teilt und lineare Zeit benötigt, um zwei Hälften zusammenzuführen. Weiterführende Lektüre:
- Mergesort ist ein effizienter, stabiler Sortieralgorithmus, der das Prinzip „Teile und herrsche“ anwendet.
- Bubble Sort in Java
- Insertion Sort in Java