Python programma sapludināšanas kārtošanai
Sapludināšanas kārtošana ir a Skaldi un iekaro algoritms. Tas sadala ievades masīvu divās daļās, izsauc sevi abām pusēm un pēc tam apvieno abas sakārtotās daļas. Funkcija sapludināt(). izmanto divu pušu sapludināšanai. Apvienošana (arr, l, m, r) ir galvenais process, kurā tiek pieņemts, ka arr[l..m] un arr[m+1..r] ir sakārtoti, un apvieno abus sakārtotos apakšmasīvus vienā.
Python programma sapludināšanas kārtošanai
Paredzētais Python kods ievieš sapludināšanas kārtošanas algoritmu, sadali un valdi šķirošanas paņēmienu. Tas sadala masīvu mazākos apakšmasīvos, sašķiro tos atsevišķi un pēc tam atkal apvieno, lai izveidotu sakārtotu masīvu. Kods ietver divas galvenās funkcijas: sapludināšanu, kas ir atbildīga par divu apakšmasu sapludināšanu, un mergeSort, kas rekursīvi sadala un kārto masīvu. Apvienošanas funkcija apvieno divus sakārtotus apakšmasīvus vienā sakārtotā masīvā. Funkcija mergeSort rekursīvi sadala masīvu uz pusēm, līdz katrā apakšmasīvā ir viens elements, un pēc tam tos sapludina, lai iegūtu galīgo sakārtoto rezultātu. Piemērā tiek kārtots masīvs, izmantojot sapludināšanas kārtošanu, un tiek izdrukāts gan sākotnējais, gan sakārtotais masīvs.
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> |
Izvade
Given array is 12 11 13 5 6 7 Sorted array is 5 6 7 11 12 13
Laika sarežģītība: O(n*log(n))
Palīgtelpa: O(n)
Lūdzu, skatiet pilnu rakstu par Sapludināt Kārtot sīkākai informācijai!
