Python-Programm für Zusammenführungssortierung
Zusammenführungssortierung ist eine Teilen und erobern Algorithmus. Es teilt das Eingabearray in zwei Hälften, ruft sich selbst für die beiden Hälften auf und führt dann die beiden sortierten Hälften zusammen. Die Funktion merge() wird zum Zusammenführen zweier Hälften verwendet. Merge(arr, l, m, r) ist ein Schlüsselprozess, der davon ausgeht, dass arr[l..m] und arr[m+1..r] sortiert sind, und die beiden sortierten Unterarrays zu einem zusammenführt.
Python-Programm für Zusammenführungssortierung
Die zur Verfügung gestellt Python Der Code implementiert den Merge-Sort-Algorithmus, eine Sortiertechnik nach dem Prinzip „Teile und herrsche“. Es zerlegt ein Array in kleinere Unterarrays, sortiert sie einzeln und fügt sie dann wieder zusammen, um ein sortiertes Array zu erstellen. Der Code enthält zwei Hauptfunktionen: merge, die für die Zusammenführung zweier Subarrays verantwortlich ist, und mergeSort, die das Array rekursiv teilt und sortiert. Die Zusammenführungsfunktion kombiniert zwei sortierte Unterarrays zu einem einzigen sortierten Array. Die Funktion mergeSort teilt das Array rekursiv in zwei Hälften, bis jedes Unterarray ein einzelnes Element enthält, und führt sie dann zusammen, um das endgültige sortierte Ergebnis zu erzielen. Das Beispiel sortiert ein Array mit Merge Sort und gibt sowohl das anfängliche als auch das sortierte Array aus.
Python3
# Python program for implementation of MergeSort> # Merges two subarrays of arr[].> # First subarray is arr[l..m]> # Second subarray is arr[m+1..r]> def> merge(arr, l, m, r):> > n1> => m> -> l> +> 1> > n2> => r> -> m> > # create temp arrays> > L> => [> 0> ]> *> (n1)> > R> => [> 0> ]> *> (n2)> > # Copy data to temp arrays L[] and R[]> > for> i> in> range> (> 0> , n1):> > L[i]> => arr[l> +> i]> > for> j> in> range> (> 0> , n2):> > 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 and j if L[i] <= R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 # Copy the remaining elements of L[], if there # are any while i arr[k] = L[i] i += 1 k += 1 # Copy the remaining elements of R[], if there # are any while j arr[k] = R[j] j += 1 k += 1 # l is for left index and r is right index of the # sub-array of arr to be sorted def mergeSort(arr, l, r): if l # Same as (l+r)//2, but avoids overflow for # large l and h m = l+(r-l)//2 # Sort first and second halves mergeSort(arr, l, m) mergeSort(arr, m+1, r) merge(arr, l, m, r) # Driver code to test above arr = [12, 11, 13, 5, 6, 7] n = len(arr) print('Given array is') for i in range(n): print('%d' % arr[i],end=' ') mergeSort(arr, 0, n-1) print('
Sorted array is') for i in range(n): print('%d' % arr[i],end=' ') # This code is contributed by Mohit Kumra> |
Ausgabe
Given array is 12 11 13 5 6 7 Sorted array is 5 6 7 11 12 13
Zeitkomplexität: O(n*log(n))
Hilfsraum: An)
Den vollständigen Artikel finden Sie unter Zusammenführen, sortieren für mehr Details!
