Python-program til Merge Sort
Merge Sort er en Del og hersk algoritme. Det opdeler input-array i to halvdele, kalder sig selv for de to halvdele og fusionerer derefter de to sorterede halvdele. Merge()-funktionen bruges til at slå to halvdele sammen. Sammenfletningen (arr, l, m, r) er en nøgleproces, der antager, at arr[l..m] og arr[m+1..r] er sorteret og flette de to sorterede sub-arrays til ét.
Python-program til Merge Sort
Den tilvejebragte Python kode implementerer Merge Sort-algoritmen, en opdel-og-hersk sorteringsteknik. Den opdeler et array i mindre underarrays, sorterer dem individuelt og fletter dem derefter sammen igen for at skabe et sorteret array. Koden omfatter to hovedfunktioner: flette, der er ansvarlig for at flette to subarrays, og mergeSort, som rekursivt opdeler og sorterer arrayet. Merge-funktionen kombinerer to sorterede underarrays til et enkelt sorteret array. MergeSort-funktionen opdeler rekursivt arrayet i to, indtil hvert underarray har et enkelt element, og fletter dem derefter for at opnå det endelige sorterede resultat. Eksemplet sorterer et array ved hjælp af Merge Sort og udskriver både de indledende og sorterede arrays.
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> |
Produktion
Given array is 12 11 13 5 6 7 Sorted array is 5 6 7 11 12 13
Tidskompleksitet: O(n*log(n))
Hjælpeplads: På)
Se venligst hele artiklen vedr Flet sortering for flere detaljer!
