Vzhľadom na súbor prvkov zistí, že permutácia týchto prvkov by viedla k najhoršiemu prípadu zlúčenia.
Asymptoticky zlúčte triedenie vždy trvá čas (n log n) čas, ale prípady, ktoré si vyžadujú viac porovnaní, vo všeobecnosti v praxi vyžadujú viac času. V podstate musíme nájsť permutáciu vstupných prvkov, ktoré by viedli k maximálnemu počtu porovnaní, keď sa triedia pomocou typického algoritmu zlúčenia.
Príklad:
tiger v porovnaní s levom
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.
Ako teraz získať vstup najhoršieho prípadu na zlúčenie zoradenia pre vstupnú sadu?
Umožňuje nám pokúsiť sa zostaviť pole zdola nahor
Nechajte triedené pole byť {12345678}.
S cieľom vygenerovať najhorší prípad zlúčenia operácie zlúčenia, ktorá mala za následok vyššie zoradené pole, by malo mať za následok maximálne porovnania. Aby to bolo možné urobiť, ľavá a pravá čiastka, ktorá sa podieľa na prevádzke zlúčenia, by mala ukladať alternatívne prvky zoradeného poľa. t. j. Teraz bude každý prvok poľa porovnávaný na najmenšom raz a to bude mať za následok maximálne porovnania. Rovnakú logiku používame aj pre ľavú a pravú čiastkovú farbu. Pre pole {1357} bude najhorší prípad, keď jeho ľavá a pravá čiastka sú {15} a {37} a pre pole {2468} Najhorší prípad sa vyskytne pre {24} a {68}.
java previesť int na reťazec
Kompletný algoritmus -
Generovaťworstcase (arr [])
- Vytvorte dve pomocné polia vľavo a doprava a uložte do nich alternatívne prvky poľa.
- Volajte generovanieworstcase pre ľavú čiastkovú čiastku: generteworstcase (vľavo)
- Volajte generovanieworstcase pre pravú čiastkovú subarray: generteworstcase (vpravo)
- Skopírujte všetky prvky ľavých a pravých čiastkových čiastok späť do pôvodného poľa.
Nižšie je implementácia myšlienky
mvc javaC++
// 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>
Výstup:
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
Časová zložitosť: O (n logn)
Pomocný priestor: o (n)
Referencie - Pretečenie zásobníka