Python programa, skirta sujungimo rūšiavimui
Sujungimo rūšiavimas yra a Skaldyk ir valdyk algoritmas. Jis padalija įvesties masyvą į dvi dalis, pasikviečia dvi dalis ir tada sujungia dvi surūšiuotas puses. Funkcija merge() naudojamas dviejų dalių sujungimui. Sujungimas (arr, l, m, r) yra pagrindinis procesas, kuriame daroma prielaida, kad arr[l..m] ir arr[m+1..r] yra surūšiuoti ir sujungia du surūšiuotus pomasyvius į vieną.
Python programa, skirta sujungimo rūšiavimui
Pateiktas Python kodas įgyvendina „Merge Sort“ algoritmą – „skaldyk ir valdyk“ rūšiavimo techniką. Jis suskaido masyvą į mažesnius pogrupius, surūšiuoja juos atskirai ir vėl sujungia, kad būtų sukurtas surūšiuotas masyvas. Kodas apima dvi pagrindines funkcijas: sujungimą, atsakingą už dviejų pogrupių sujungimą, ir mergeSort, kuris rekursyviai padalija ir rūšiuoja masyvą. Sujungimo funkcija sujungia dvi surūšiuotas pogrupes į vieną surūšiuotą masyvą. Funkcija mergeSort rekursyviai padalija masyvą per pusę, kol kiekvienas pogrupis turi vieną elementą, tada juos sujungia, kad gautų galutinį surūšiuotą rezultatą. Pavyzdyje masyvas rūšiuojamas naudojant sujungimo rūšiavimą ir spausdinamas tiek pradinis, tiek surūšiuotas masyvas.
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> |
Išvestis
Given array is 12 11 13 5 6 7 Sorted array is 5 6 7 11 12 13
Laiko sudėtingumas: O(n*log(n))
Pagalbinė erdvė: O(n)
Peržiūrėkite visą straipsnį apie Sujungti Rūšiuoti daugiau detalių!
