Rumah >pembangunan bahagian belakang >C++ >Cari pilih atur yang membawa kepada senario kes terburuk jenis gabungan dalam C
Untuk set elemen tertentu, tentukan susunan mana yang akan membawa kepada kes terburuk jenis gabungan?
Kami tahu bahawa secara asimptotik, isihan cantum sentiasa mengambil masa O(n log n), tetapi dalam amalan, kes yang memerlukan lebih banyak perbandingan biasanya mengambil lebih banyak masa. Sekarang kita pada asasnya perlu menentukan susunan elemen input yang memaksimumkan bilangan perbandingan apabila melaksanakan algoritma isihan gabungan biasa. . 23 13 21 17 25 12 20 16 24 14 22 18 26
KaedahKami mengkaji cara membina set input kes terburuk untuk isihan gabungan?
Sekarang kita cuba membina tatasusunan dengan cara bawah ke atas
Sekarang biarkan tatasusunan yang diisih ialah {11, 12, 13, 14, 15, 16, 17, 18}.
Algoritma Penuh
GenerateWorstCase(arr[])Kami memanggil GenerateWorstCase - GenerateWorstCase (kiri) pada sub-array kiri
Kami memanggil GenerateWorstCase pada sub-array kanan - GenerateWorstCase (kanan)
kita// 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; }
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
Atas ialah kandungan terperinci Cari pilih atur yang membawa kepada senario kes terburuk jenis gabungan dalam C. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!