logo

TechCodeview

Cerqueu una permutació que provoqui el pitjor dels casos de combinació

Tenint en compte un conjunt d’elements, quina permutació d’aquests elements tindria com a resultat el pitjor dels casos.
La combinació asimptòtica sempre requereix temps O (N log N), però els casos que requereixen més comparacions generalment triguen més temps a la pràctica. Bàsicament hem de trobar una permutació d’elements d’entrada que comportessin el màxim nombre de comparacions quan s’ordenin mitjançant un algorisme típic d’ordenació de fusions.

Exemple:  



java converteix nombre enter en cadena 
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.

Ara, com obtenir el pitjor dels casos per a una obra de combinació per a un conjunt d'entrada?

Ens permet intentar construir la matriu de baix a baix
Deixeu que la matriu ordenada sigui {12345678}.

Per tal de generar el pitjor dels casos de combinar, l’operació de combinació que va resultar en una matriu ordenada anteriorment hauria de donar lloc a les comparacions màximes. Per tal de fer-ho, la sub-matriu esquerra i dreta implicada en l'operació de combinació ha de guardar elements alternatius de la matriu ordenada. és a dir, la sub-array esquerra hauria de ser {1357} i la sub-array dreta hauria de ser {2468}. Ara es compararan tots els elements de matriu una vegada i això tindrà com a resultat comparacions màximes. Apliquem la mateixa lògica per a la sub-matriu esquerra i dreta. Per a Array {1357} El pitjor dels casos serà quan la seva sub-array esquerra i dreta siguin {15} i {37} respectivament i per a la matriu {2468} el pitjor cas es produirà per a {24} i {68}.



Algoritme complet -
GenerateWorscase (arr [])  

  1. Creeu dues matrius auxiliars a l'esquerra i a la dreta i emmagatzemeu -hi elements de matriu alternatius.
  2. Truca Generatworscase per a la subarray esquerra: GenerateWorscase (a l'esquerra)
  3. Truca GenerateWorscase per a la subarraia dreta: GenerateWorscase (a la dreta)
  4. Copieu tots els elements de les subarres de l'esquerra i la dreta de nou a la matriu original.

A continuació es mostra la implementació de la idea

string.valueof
C++ 
// C++ program to generate Worst Case // of Merge Sort #include    using namespace std; // Function to print an array void printArray(int A[] int size) {  for(int i = 0; i < size; i++)  {  cout << A[i] << ' ';  }  cout << endl; } // Function to join left and right subarray int 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 int 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 int generateWorstCase(int arr[] int l  int r) {  if (l < r)  {  int m = l + (r - l) / 2;  // Create two auxiliary arrays  int left[m - l + 1];  int right[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 code int main() {    // Sorted array  int arr[] = { 1 2 3 4 5 6 7 8 9  10 11 12 13 14 15 16 };    int n = sizeof(arr) / sizeof(arr[0]);  cout << 'Sorted array is n';  printArray(arr n);  // Generate Worst Case of Merge Sort  generateWorstCase(arr 0 n - 1);  cout << 'nInput array that will result '  << 'in worst case of merge sort is n';    printArray(arr n);  return 0; } // This code is contributed by Mayank Tyagi
C 
// C program to generate Worst Case of Merge Sort  #include   #include   // Function to print an array  void printArray(int A[] int size)  {   for (int i = 0; i < size; i++)   printf('%d ' A[i]);   printf('n');  }  // Function to join left and right subarray  int join(int arr[] int left[] int right[]   int l int m int r)  {   int i; // Used in second loop   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  int 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  int generateWorstCase(int arr[] int l int r)  {   if (l < r)   {   int m = l + (r - l) / 2;   // create two auxiliary arrays   int left[m - l + 1];   int right[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 code  int main()  {   // Sorted array   int arr[] = { 1 2 3 4 5 6 7 8 9   10 11 12 13 14 15 16 };   int n = sizeof(arr) / sizeof(arr[0]);   printf('Sorted array is n');   printArray(arr n);   // generate Worst Case of Merge Sort   generateWorstCase(arr 0 n - 1);   printf('nInput array that will result in '  'worst case of merge sort is n');   printArray(arr n);   return 0;  }
Java 
// 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 
# 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# 
// 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
JavaScript 
<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>

Sortida:  



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

Complexitat del temps: O (N LOGN)
Espai auxiliar: O (N)
Referències - Desbordament de pila