Rumah >pembangunan bahagian belakang >C++ >Cari pilih atur yang membawa kepada senario kes terburuk jenis gabungan dalam C

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

WBOY
WBOYke hadapan
2023-08-28 16:09:06951semak imbas

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

GenerateWorstCase(arr[])

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

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!

Kenyataan:
Artikel ini dikembalikan pada:tutorialspoint.com. Jika ada pelanggaran, sila hubungi admin@php.cn Padam