Trouvez la permutation qui conduit au pire des cas de tri par fusion en C

Concept

Pour un ensemble d'éléments donné, déterminer quel arrangement conduira au pire scénario de tri par fusion ?

Nous savons que asymptotiquement, le tri par fusion prend toujours un temps O(n log n), mais en pratique, les cas qui nécessitent plus de comparaisons prennent généralement plus de temps. Nous devons maintenant essentiellement déterminer un arrangement d’éléments d’entrée qui maximise le nombre de comparaisons lors de la mise en œuvre d’un algorithme de tri par fusion typique.

Exemple

Considérez l'ensemble d'éléments suivant comme un tableau trié 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Le tableau d'entrée qui donne le pire cas de tri par fusion est 11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26

Méthode

Nous étudions comment construire le pire ensemble d'entrées pour le tri par fusion ?

Maintenant, nous essayons de construire le tableau de manière ascendante.

Maintenant, laissez le tableau trié être {11, 12, 13, 14, 15, 16, 17, 18}.

Pour construire le pire des cas pour le tri par fusion, l'opération de fusion résultant dans le tableau trié ci-dessus devrait donner lieu au plus grand nombre de comparaisons. Par conséquent, le sous-tableau gauche et le sous-tableau droit participant à l'opération de fusion doivent stocker alternativement les éléments du tableau trié. Le sous-tableau gauche doit être {11, 13, 15, 17} et le sous-tableau droit doit être {12, 14, 16. , 18 }. De cette façon, chaque élément du tableau sera comparé au moins une fois, ce qui entraînera un nombre maximum de comparaisons. Nous implémentons maintenant la même logique pour le sous-tableau de gauche et le sous-tableau de droite. Pour le tableau {11, 13, 15, 17}, le pire des cas se produit lorsque son sous-tableau gauche est {11, 15} et son sous-tableau droit est {13, 17}. Pour le tableau {12, 14, 16, 18}. , Le pire des cas se produit à {12, 14} et {16, 18}.

Algorithme complet

GenerateWorstCase(arr[])

• Maintenant, nous créons deux tableaux auxiliaires à gauche et à droite et y stockons des éléments de tableau alternés.

• Nous appelons GenerateWorstCase - GenerateWorstCase (à gauche)

• Nous appelons GenerateWorstCase - GenerateWorstCase (à droite) sur le sous-tableau droit

• Maintenant, nous copions tous les éléments du sous-tableau gauche et du sous-tableau droit. Renvoyons le tableau d'origine.

Exemple

Démonstration

// C program to generate Worst Case of Merge Sort
#include <stdlib.h>
#include <stdio.h>
// Indicates function to print an array
void printArray(int A1[], int size1){
   for (int i = 0; i < size1; i++)
      printf("%d ", A1[i]);
   printf("</p><p>");
}
// Indicates function to join left and right subarray
int join(int arr1[], int left1[], int right1[],
int l1, int m1, int r1){
   int i; // So used in second loop
   for (i = 0; i <= m1 - l1; i++)
      arr1[i] = left1[i];
   for (int j = 0; j < r1 - m1; j++)
      arr1[i + j] = right1[j];
}
// Indicates function to store alternate elemets in left
// and right subarray
int split(int arr1[], int left1[], int right1[],
int l1, int m1, int r1){
   for (int i = 0; i <= m1 - l1; i++)
      left1[i] = arr1[i * 2];
   for (int i = 0; i < r1 - m1; i++)
      right1[i] = arr1[i * 2 + 1];
}
// Indicates function to generate Worst Case of Merge Sort
int generateWorstCase(int arr1[], int l1, int r1){
   if (l1 < r1){
      int m1 = l1 + (r1 - l1) / 2;
      // creating two auxillary arrays
      int left1[m1 - l1 + 1];
      int right1[r1 - m1];
      // Storing alternate array elements in left
      // and right subarray
      split(arr1, left1, right1, l1, m1, r1);
      // Recursing first and second halves
      generateWorstCase(left1, l1, m1);
      generateWorstCase(right1, m1 + 1, r1);
      // joining left and right subarray
      join(arr1, left1, right1, l1, m1, r1);
   }
}
// Driver code
int main(){
   // Initializes sorted array
   int arr1[] = { 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 };
   int n1 = sizeof(arr1) / sizeof(arr1[0]);
   printf("Sorted array is </p><p>");
   printArray(arr1, n1);
   // generating worst Case of Merge Sort
   generateWorstCase(arr1, 0, n1 - 1);
   printf("</p><p>Input array that will result in " "worst case of merge sort is </p><p>");
   printArray(arr1, n1);
   return 0;
}

Sortie

Sorted array is
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Input array that will result in worst case of merge sort is
11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!