C++에서 Merge Sort의 최악의 경우를 일으키는 순열 찾기

요소 집합이 있다고 가정합니다. 우리는 이러한 요소의 어떤 순열이 병합 정렬의 최악의 경우를 초래하는지 찾아야 합니까? 점근적으로 알고 있듯이 병합 정렬은 항상 O(n log n) 시간을 소비하지만 어떤 경우에는 더 많은 비교가 필요하고 더 많은 시간을 소비합니다. 여기에서 일반적인 병합 정렬 알고리즘을 구현하여 정렬할 때 더 많은 비교가 필요한 입력 요소의 순열을 찾아야 합니다.

따라서 입력이 [11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26] 과 같으면 출력은 [11,19 ,15,23,13,21,17,25,12,20,16,24,14,22,18,26].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• merge() 함수를 정의하면 배열 arr, 배열 왼쪽, 배열 오른쪽, l_index, m_index, r_index,
• 초기화 i의 경우:=0, i <=m_index - l_index일 때 업데이트(i를 1만큼 증가), 수행 -
  • arr[i] :=왼쪽[i]
• j 초기화의 경우:=0, j
• arr[i + j] =오른쪽[j]

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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);
}

입력

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

출력

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