Python-programma voor samenvoegsortering
Samenvoegsortering is een Verdeel en heers algoritme. Het verdeelt de invoerarray in twee helften, roept zichzelf op voor de twee helften en voegt vervolgens de twee gesorteerde helften samen. De functie merge(). wordt gebruikt voor het samenvoegen van twee helften. De merge(arr, l, m, r) is een sleutelproces dat ervan uitgaat dat arr[l..m] en arr[m+1..r] zijn gesorteerd en de twee gesorteerde subarrays samenvoegt tot één.
Python-programma voor samenvoegsortering
De verstrekte Python code implementeert het Merge Sort-algoritme, een verdeel-en-heers-sorteertechniek. Het verdeelt een array in kleinere subarrays, sorteert ze afzonderlijk en voegt ze vervolgens weer samen om een gesorteerde array te creëren. De code bevat twee hoofdfuncties: merge, verantwoordelijk voor het samenvoegen van twee subarrays, en mergeSort, dat de array recursief verdeelt en sorteert. De samenvoegfunctie combineert twee gesorteerde subarrays tot één gesorteerde array. De functie mergeSort splitst de array recursief in tweeën totdat elke subarray een enkel element bevat, en voegt deze vervolgens samen om het uiteindelijke gesorteerde resultaat te bereiken. In het voorbeeld wordt een array gesorteerd met behulp van Merge Sort en worden zowel de initiële als de gesorteerde arrays afgedrukt.
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> |
Uitvoer
Given array is 12 11 13 5 6 7 Sorted array is 5 6 7 11 12 13
Tijdcomplexiteit: O(n*log(n))
Hulpruimte: Op)
Raadpleeg het volledige artikel op Sortering samenvoegen voor meer details!
