Givet et sæt elementer finder ud af, hvilken permutation af disse elementer ville resultere i værste tilfælde af fusion.
Asymptotisk fletter sortering altid o (n log n) tid, men de tilfælde, der kræver flere sammenligninger, tager generelt mere tid i praksis. Vi er dybest set nødt til at finde en permutation af inputelementer, der ville føre til maksimalt antal sammenligninger, når de sorteres ved hjælp af en typisk fusionssorteringsalgoritme.
Eksempel:
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.
Nu hvordan får man worst case -input til fusion sortering til et inputsæt?
Lader os prøve at bygge matrixen på bunden af måde
Lad det sorterede array være {12345678}.
For at generere det værste tilfælde af fusion sorterer fletningsoperationen, der resulterede i ovenfor sorteret array, skulle resultere i maksimale sammenligninger. For at gøre det skal den venstre og højre under-array, der er involveret i fletningsoperation, gemme alternative elementer af sorteret array. dvs. venstre under-array skal være {1357}, og højre under-array skal være {2468}. Nu sammenlignes hvert element af array en gang en gang, og det vil resultere i maksimale sammenligninger. Vi anvender også den samme logik til venstre og højre under-array. For Array {1357} vil det værste tilfælde være, når dens venstre og højre under-array er henholdsvis {15} og {37} og for array {2468} det værste tilfælde vil forekomme for {24} og {68}.
Komplet algoritme -
Genererworstcase (arr [])
- Opret to hjælpestillinger til venstre og højre, og opbevar alternative array -elementer i dem.
- Ring Generererworstcase til venstre underrejsen: Genererworstcase (til venstre)
- Ring GeneryWorstcase til højre underforening: GenerationWorstcase (til højre)
- Kopier alle elementer i venstre og højre undergray tilbage til den originale array.
Nedenfor er implementeringen af ideen
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>
Produktion:
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
Tidskompleksitet: O (n Logn)
Hjælpeplads: O (n)
Referencer - Stack Overflow