Tìm một hoán vị gây ra trường hợp xấu nhất của Merge Sort trong C ++

Giả sử chúng ta có một tập hợp các phần tử; chúng ta phải tìm xem hoán vị nào của các phần tử này sẽ dẫn đến trường hợp xấu nhất là Merge Sort? Như chúng ta đã biết về mặt tiệm cận, sắp xếp hợp nhất luôn tiêu tốn O (n log n) thời gian, nhưng một số trường hợp cần nhiều so sánh hơn và tiêu tốn nhiều thời gian hơn. Ở đây, chúng ta phải tìm một hoán vị của các phần tử đầu vào sẽ yêu cầu số lượng so sánh cao hơn khi được sắp xếp thực hiện thuật toán Sắp xếp Hợp nhất điển hình.

Vì vậy, nếu đầu vào là [11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26], thì đầu ra sẽ là [11,19 , 15,23,13,21,17,25,12,20,16,24,14,22,18,26].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm merge (), điều này sẽ lấy mảng arr, mảng bên trái, mảng bên phải, l_index, m_index, r_index,
• để khởi tạo i:=0, khi tôi <=m_index - l_index, cập nhật (tăng i lên 1), thực hiện -
  • arr [i]:=left [i]
• để khởi tạo j:=0, khi j
• arr [i + j] =right [j]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
void display(int A[], int size) {
   for (int i = 0; i < size; i++)
      cout << A[i] << " ";
   cout << endl;
}
int merge(int arr[], int left[], int right[],int l_index, int m_index, int r_index) {
   int i;
   for (i = 0; i <= m_index - l_index; i++)
      arr[i] = left[i];
   for (int j = 0; j < r_index - m_index; j++)
      arr[i + j] = right[j];
}
int divide(int arr[], int left[], int right[], int l_index, int m_index, int r_index) {
   for (int i = 0; i <= m_index - l_index; i++)
      left[i] = arr[i * 2];
   for (int i = 0; i < r_index - m_index; i++)
      right[i] = arr[i * 2 + 1];
}
int gen_worst_seq(int arr[], int l_index, int r_index) {
   if (l_index < r_index) {
      int m_index = l_index + (r_index - l_index) / 2;
      int left[m_index - l_index + 1];
      int right[r_index - m_index];
      divide(arr, left, right, l_index, m_index, r_index);
      gen_worst_seq(left, l_index, m_index);
      gen_worst_seq(right, m_index + 1, r_index);
      merge(arr, left, right, l_index, m_index, r_index);
   }
}
int main() {
   int arr[] = {11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26};
   int n = sizeof(arr) / sizeof(arr[0]);
   gen_worst_seq(arr, 0, n - 1);
   display(arr, n);
}

Đầu vào

11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26

Đầu ra

11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26