Gegeven een reeks elementen vinden welke permutatie van deze elementen zou resulteren in het ergste geval van samenvoeging.
Asymptotisch samenvoegen sorteert altijd o (n log n) tijd, maar de gevallen die meer vergelijkingen vereisen, kosten in de praktijk over het algemeen meer tijd. We moeten in principe een permutatie vinden van input -elementen die zouden leiden tot maximaal aantal vergelijkingen wanneer gesorteerd met behulp van een typisch samenvoegingsalgoritme.
Voorbeeld:
Consider the below set of elements
{1 2 3 4 5 6 7 8 9 10 11 12
13 14 15 16}
Below permutation of the set causes 153
comparisons.
{1 9 5 13 3 11 7 15 2 10 6
14 4 12 8 16}
And an already sorted permutation causes
30 comparisons.
Hoe krijg je nu worst case input voor samenvoegen SORT voor een inputset?
Laten we proberen de array op de onderste manier te bouwen
Laat de gesorteerde array {12345678} zijn.
Om het slechtste geval van samenvoeging te genereren, zou de samenvoeging die resulteerde in een bovenstaande gesorteerde array zou moeten resulteren in maximale vergelijkingen. Om dit te doen, moet de linker- en rechter sub-array die betrokken is bij de samenvoegingsoperatie alternatieve elementen opslaan van gesorteerde array. d.w.z. linker sub-array moet {1357} zijn en de rechter sub-array moet {2468} zijn. Nu wordt elk eenmaal op het minst op het minste element vergeleken en dat zal resulteren in maximale vergelijkingen. We passen ook dezelfde logica toe voor linker en rechts sub-array. Voor array {1357} zal het slechtste geval zijn wanneer de linker en rechter sub-array respectievelijk {15} en {37} zijn en voor array {2468} Het slechtste geval zal plaatsvinden voor {24} en {68}.
Hoe weet je of iemand je op Android heeft geblokkeerd?
Compleet algoritme -
GenerateWorStCase (arr [])
- Maak twee hulparrays links en rechts en bewaar alternatieve array -elementen erin.
- Bel GenerateWorStCase voor Left SubArray: GenerateWorStCase (links)
- Bel GenerateWorStCase voor Right SubArray: GenerateWorStCase (rechts)
- Kopieer alle elementen van linker- en rechter subarrays terug naar de originele array.
Hieronder is de implementatie van het idee
C++// C++ program to generate Worst Case // of Merge Sort #include
// C program to generate Worst Case of Merge Sort #include
// Java program to generate Worst Case of Merge Sort import java.util.Arrays; class GFG { // Function to join left and right subarray static void join(int arr[] int left[] int right[] int l int m int r) { int i; for (i = 0; i <= m - l; i++) arr[i] = left[i]; for (int j = 0; j < r - m; j++) arr[i + j] = right[j]; } // Function to store alternate elements in left // and right subarray static void split(int arr[] int left[] int right[] int l int m int r) { for (int i = 0; i <= m - l; i++) left[i] = arr[i * 2]; for (int i = 0; i < r - m; i++) right[i] = arr[i * 2 + 1]; } // Function to generate Worst Case of Merge Sort static void generateWorstCase(int arr[] int l int r) { if (l < r) { int m = l + (r - l) / 2; // create two auxiliary arrays int[] left = new int[m - l + 1]; int[] right = new int[r - m]; // Store alternate array elements in left // and right subarray split(arr left right l m r); // Recurse first and second halves generateWorstCase(left l m); generateWorstCase(right m + 1 r); // join left and right subarray join(arr left right l m r); } } // driver program public static void main (String[] args) { // sorted array int arr[] = { 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 }; int n = arr.length; System.out.println('Sorted array is'); System.out.println(Arrays.toString(arr)); // generate Worst Case of Merge Sort generateWorstCase(arr 0 n - 1); System.out.println('nInput array that will result in n'+ 'worst case of merge sort is n'); System.out.println(Arrays.toString(arr)); } } // Contributed by Pramod Kumar
# Python program to generate Worst Case of Merge Sort # Function to join left and right subarray def join(arr left right l m r): i = 0; for i in range(m-l+1): arr[i] = left[i]; i+=1; for j in range(r-m): arr[i + j] = right[j]; # Function to store alternate elements in left # and right subarray def split(arr left right l m r): for i in range(m-l+1): left[i] = arr[i * 2]; for i in range(r-m): right[i] = arr[i * 2 + 1]; # Function to generate Worst Case of Merge Sort def generateWorstCase(arr l r): if (l < r): m = l + (r - l) // 2; # create two auxiliary arrays left = [0 for i in range(m - l + 1)]; right = [0 for i in range(r-m)]; # Store alternate array elements in left # and right subarray split(arr left right l m r); # Recurse first and second halves generateWorstCase(left l m); generateWorstCase(right m + 1 r); # join left and right subarray join(arr left right l m r); # driver program if __name__ == '__main__': # sorted array arr = [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]; n = len(arr); print('Sorted array is'); print(arr); # generate Worst Case of Merge Sort generateWorstCase(arr 0 n - 1); print('nInput array that will result in n' + 'worst case of merge sort is '); print(arr); # This code contributed by shikhasingrajput
// C# program to generate Worst Case of // Merge Sort using System; class GFG { // Function to join left and right subarray static void join(int []arr int []left int []right int l int m int r) { int i; for (i = 0; i <= m - l; i++) arr[i] = left[i]; for (int j = 0; j < r - m; j++) arr[i + j] = right[j]; } // Function to store alternate elements in // left and right subarray static void split(int []arr int []left int []right int l int m int r) { for (int i = 0; i <= m - l; i++) left[i] = arr[i * 2]; for (int i = 0; i < r - m; i++) right[i] = arr[i * 2 + 1]; } // Function to generate Worst Case of // Merge Sort static void generateWorstCase(int []arr int l int r) { if (l < r) { int m = l + (r - l) / 2; // create two auxiliary arrays int[] left = new int[m - l + 1]; int[] right = new int[r - m]; // Store alternate array elements // in left and right subarray split(arr left right l m r); // Recurse first and second halves generateWorstCase(left l m); generateWorstCase(right m + 1 r); // join left and right subarray join(arr left right l m r); } } // driver program public static void Main () { // sorted array int []arr = { 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 }; int n = arr.Length; Console.Write('Sorted array isn'); for(int i = 0; i < n; i++) Console.Write(arr[i] + ' '); // generate Worst Case of Merge Sort generateWorstCase(arr 0 n - 1); Console.Write('nInput array that will ' + 'result in n worst case of' + ' merge sort is n'); for(int i = 0; i < n; i++) Console.Write(arr[i] + ' '); } } // This code is contributed by Smitha
<script> // javascript program to generate Worst Case // of Merge Sort // Function to print an array function printArray(Asize) { for(let i = 0; i < size; i++) { document.write(A[i] + ' '); } } // Function to join left and right subarray function join(arrleftrightlmr) { let i; for(i = 0; i <= m - l; i++) arr[i] = left[i]; for(let j = 0; j < r - m; j++) { arr[i + j] = right[j]; } } // Function to store alternate elements in // left and right subarray function split(arrleftrightlmr) { for(let i = 0; i <= m - l; i++) left[i] = arr[i * 2]; for(let i = 0; i < r - m; i++) right[i] = arr[i * 2 + 1]; } // Function to generate Worst Case // of Merge Sort function generateWorstCase(arrlr) { if (l < r) { let m = l + parseInt((r - l) / 2 10); // Create two auxiliary arrays let left = new Array(m - l + 1); let right = new Array(r - m); left.fill(0); right.fill(0); // Store alternate array elements // in left and right subarray split(arr left right l m r); // Recurse first and second halves generateWorstCase(left l m); generateWorstCase(right m + 1 r); // Join left and right subarray join(arr left right l m r); } } let arr = [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ]; let n = arr.length; document.write('Sorted array is' + ''); printArray(arr n); // Generate Worst Case of Merge Sort generateWorstCase(arr 0 n - 1); document.write('' + 'Input array that will result ' + 'in worst case of merge sort is' + ''); printArray(arr n); // This code is contributed by vaibhavrabadiya117. </script>
Uitvoer:
Sorted array is
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Input array that will result in worst
case of merge sort is
1 9 5 13 3 11 7 15 2 10 6 14 4 12 8 16
Tijdcomplexiteit: O (n logn)
Hulpruimte: O (n)
REFERENTIES - Stapel overloop