Cari pilih atur yang membawa kepada senario kes terburuk jenis gabungan dalam C

Konsep

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}.

Untuk membina senario terburuk untuk isihan cantum, operasi cantum yang menghasilkan tatasusunan yang diisih di atas harus menghasilkan perbandingan yang paling banyak. Oleh itu, subarray kiri dan subarray kanan yang mengambil bahagian dalam operasi cantuman hendaklah secara bergilir-gilir menyimpan unsur tatasusunan yang diisih Subarray kiri hendaklah {11, 13, 15, 17}, dan subarray kanan hendaklah {12, 14, 16. , 18 }. Dengan cara ini, setiap elemen tatasusunan akan dibandingkan sekurang-kurangnya sekali, menghasilkan bilangan perbandingan maksimum. Sekarang kita melaksanakan logik yang sama untuk subarray kiri dan kanan juga. Untuk tatasusunan {11, 13, 15, 17}, kes terburuk berlaku apabila subarray kiri ialah {11, 15} dan subarray kanannya ialah {13, 17}. Untuk tatasusunan {12, 14, 16, 18} , Kes terburuk berlaku pada {12, 14} dan {16, 18}.

Algoritma Penuh

Kini kami mencipta dua tatasusunan tambahan kiri dan kanan dan menyimpan elemen tatasusunan berselang-seli di dalamnya.

Kami memanggil GenerateWorstCase - GenerateWorstCase (kiri) pada sub-array kiri

• Kami memanggil GenerateWorstCase pada sub-array kanan - GenerateWorstCase (kanan)

  kita
• salin semua elemen sub-array -array dan sub-array kanan Kembalikan tatasusunan asal.

• Contoh
  Demonstrasi

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

Salin selepas log masuk
• Output

  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

  Salin selepas log masuk

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!