Finden Sie die Permutation, die zum Worst-Case-Szenario der Zusammenführungssortierung in C führt

Konzept

Bestimmen Sie für einen bestimmten Satz von Elementen, welche Anordnung im schlimmsten Fall zum Zusammenführungssortieren führt?

Wir wissen, dass die Zusammenführungssortierung asymptotisch immer O(n log n) Zeit benötigt, aber in der Praxis nehmen Fälle, die mehr Vergleiche erfordern, normalerweise mehr Zeit in Anspruch. Jetzt müssen wir grundsätzlich eine Anordnung von Eingabeelementen bestimmen, die die Anzahl der Vergleiche maximiert, wenn ein typischer Merge-Sort-Algorithmus implementiert wird.

Beispiel

Betrachten Sie den folgenden Satz von Elementen als sortiertes Array 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Das Eingabearray, das im schlimmsten Fall der Zusammenführungssortierung resultiert, ist 11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26

Methode

Wir untersuchen, wie man den Worst-Case-Eingabesatz für die Zusammenführungssortierung erstellt.

Jetzt versuchen wir, das Array von unten nach oben aufzubauen.

Das sortierte Array sei nun {11, 12, 13, 14, 15, 16, 17, 18}.

Um das Worst-Case-Szenario für die Zusammenführungssortierung zu konstruieren, sollte die Zusammenführungsoperation, die zum oben sortierten Array führt, zu den meisten Vergleichen führen. Daher sollten das linke Subarray und das rechte Subarray, die an der Zusammenführungsoperation teilnehmen, abwechselnd die Elemente des sortierten Arrays speichern. Das linke Subarray sollte {11, 13, 15, 17} sein und das rechte Subarray sollte {12, 14, 16 sein , 18 }. Auf diese Weise wird jedes Element des Arrays mindestens einmal verglichen, was zu einer maximalen Anzahl von Vergleichen führt. Jetzt implementieren wir dieselbe Logik auch für das linke und rechte Subarray. Für das Array {11, 13, 15, 17} tritt der schlimmste Fall auf, wenn sein linkes Unterarray {11, 15} und sein rechtes Unterarray {13, 17} ist. Für das Array {12, 14, 16, 18}. , Der schlimmste Fall tritt bei {12, 14} und {16, 18} auf.

Vollständiger Algorithmus

GenerateWorstCase(arr[])

• Jetzt erstellen wir zwei Hilfsarrays links und rechts und speichern abwechselnd Array-Elemente darin.

• Wir rufen GenerateWorstCase - GenerateWorstCase (links) auf

• Wir rufen GenerateWorstCase - GenerateWorstCase (rechts) für das rechte Subarray auf

• Jetzt kopieren wir alle Elemente des linken Subarrays und des rechten Subarrays und geben das ursprüngliche Array zurück.

Beispiel

Demonstration

// 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;
}

Ausgabe

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

Das obige ist der detaillierte Inhalt vonFinden Sie die Permutation, die zum Worst-Case-Szenario der Zusammenführungssortierung in C führt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!