최악의 병합 정렬을 일으키는 순열을 찾으십시오.
요소 세트가 주어지면 이러한 요소의 순열이 최악의 병합 정렬을 초래할 것입니다.
비대칭 적으로 정렬을 병합하는 데 항상 O (n log n) 시간이 걸리지 만 더 많은 비교가 필요한 경우 일반적으로 더 많은 시간이 걸립니다. 기본적으로 일반적인 병합 정렬 알고리즘을 사용하여 정렬 할 때 최대 비교 수로 이어지는 입력 요소의 순열을 찾아야합니다.
예:
Consider the below set of elements
{1 2 3 4 5 6 7 8 9 10 11 12
13 14 15 16}
Below permutation of the set causes 153
comparisons.
{1 9 5 13 3 11 7 15 2 10 6
14 4 12 8 16}
And an already sorted permutation causes
30 comparisons.이제 입력 세트의 병합 정렬에 대한 최악의 입력을 얻는 방법은 무엇입니까?
배열을 최상의 방식으로 빌드하려고합니다.
정렬 된 배열을 {12345678}로 두십시오.병합의 최악의 사례를 생성하려면 위에서 분류 된 배열을 초래 한 병합 작업은 최대의 비교를 초래해야합니다. 그렇게하려면 병합 작업에 관련된 왼쪽 및 오른쪽 하위 배열은 정렬 된 배열의 대체 요소를 저장해야합니다. 즉, 왼쪽 하위 배열은 {1357}이어야하며 오른쪽 하위 배열은 {2468}이어야합니다. 이제 배열의 모든 요소는 한 번에 한 번 비교되며 최대의 비교가 발생합니다. 왼쪽 및 오른쪽 하위 배열에 대해서도 동일한 논리를 적용합니다. 배열 {1357}의 경우 최악의 경우는 왼쪽과 오른쪽 하위 배열이 각각 {15} 및 {37}이고 배열 {2468}의 경우 {24} 및 {68}의 경우 최악의 경우가 발생합니다.
완전한 알고리즘 -
GenerateWorstcase (arr [])
- 왼쪽과 오른쪽으로 두 개의 보조 배열을 만들고 대체 어레이 요소를 저장하십시오.
- 왼쪽 서브 어레이에 대한 Call GenerateWorstcase : GenerateWorstcase (왼쪽)
- 오른쪽 서브 어레이에 대한 Call GenerateWorstcase : GenerateWorstcase (오른쪽)
- 왼쪽 및 오른쪽 서브 어레이의 모든 요소를 원래 배열로 복사하십시오.
아래는 아이디어의 구현입니다
C++C// C++ program to generate Worst Case // of Merge Sort #includeusing namespace std ; // Function to print an array void printArray ( int A [] int size ) { for ( int i = 0 ; i < size ; i ++ ) { cout < < A [ i ] < < ' ' ; } cout < < endl ; } // Function to join left and right subarray int join ( int arr [] int left [] int right [] int l int m int r ) { int i ; for ( i = 0 ; i <= m - l ; i ++ ) arr [ i ] = left [ i ]; for ( int j = 0 ; j < r - m ; j ++ ) { arr [ i + j ] = right [ j ]; } } // Function to store alternate elements in // left and right subarray int split ( int arr [] int left [] int right [] int l int m int r ) { for ( int i = 0 ; i <= m - l ; i ++ ) left [ i ] = arr [ i * 2 ]; for ( int i = 0 ; i < r - m ; i ++ ) right [ i ] = arr [ i * 2 + 1 ]; } // Function to generate Worst Case // of Merge Sort int generateWorstCase ( int arr [] int l int r ) { if ( l < r ) { int m = l + ( r - l ) / 2 ; // Create two auxiliary arrays int left [ m - l + 1 ]; int right [ r - m ]; // Store alternate array elements // in left and right subarray split ( arr left right l m r ); // Recurse first and second halves generateWorstCase ( left l m ); generateWorstCase ( right m + 1 r ); // Join left and right subarray join ( arr left right l m r ); } } // Driver code int main () { // Sorted array int arr [] = { 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); cout < < 'Sorted array is n ' ; printArray ( arr n ); // Generate Worst Case of Merge Sort generateWorstCase ( arr 0 n - 1 ); cout < < ' n Input array that will result ' < < 'in worst case of merge sort is n ' ; printArray ( arr n ); return 0 ; } // This code is contributed by Mayank Tyagi Java// C program to generate Worst Case of Merge Sort #include#include // Function to print an array void printArray ( int A [] int size ) { for ( int i = 0 ; i < size ; i ++ ) printf ( '%d ' A [ i ]); printf ( ' n ' ); } // Function to join left and right subarray int join ( int arr [] int left [] int right [] int l int m int r ) { int i ; // Used in second loop for ( i = 0 ; i <= m - l ; i ++ ) arr [ i ] = left [ i ]; for ( int j = 0 ; j < r - m ; j ++ ) arr [ i + j ] = right [ j ]; } // Function to store alternate elements in left // and right subarray int split ( int arr [] int left [] int right [] int l int m int r ) { for ( int i = 0 ; i <= m - l ; i ++ ) left [ i ] = arr [ i * 2 ]; for ( int i = 0 ; i < r - m ; i ++ ) right [ i ] = arr [ i * 2 + 1 ]; } // Function to generate Worst Case of Merge Sort int generateWorstCase ( int arr [] int l int r ) { if ( l < r ) { int m = l + ( r - l ) / 2 ; // create two auxiliary arrays int left [ m - l + 1 ]; int right [ r - m ]; // Store alternate array elements in left // and right subarray split ( arr left right l m r ); // Recurse first and second halves generateWorstCase ( left l m ); generateWorstCase ( right m + 1 r ); // join left and right subarray join ( arr left right l m r ); } } // Driver code int main () { // Sorted array int arr [] = { 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); printf ( 'Sorted array is n ' ); printArray ( arr n ); // generate Worst Case of Merge Sort generateWorstCase ( arr 0 n - 1 ); printf ( ' n Input array that will result in ' 'worst case of merge sort is n ' ); printArray ( arr n ); return 0 ; } Python// Java program to generate Worst Case of Merge Sort import java.util.Arrays ; class GFG { // Function to join left and right subarray static void join ( int arr [] int left [] int right [] int l int m int r ) { int i ; for ( i = 0 ; i <= m - l ; i ++ ) arr [ i ] = left [ i ] ; for ( int j = 0 ; j < r - m ; j ++ ) arr [ i + j ] = right [ j ] ; } // Function to store alternate elements in left // and right subarray static void split ( int arr [] int left [] int right [] int l int m int r ) { for ( int i = 0 ; i <= m - l ; i ++ ) left [ i ] = arr [ i * 2 ] ; for ( int i = 0 ; i < r - m ; i ++ ) right [ i ] = arr [ i * 2 + 1 ] ; } // Function to generate Worst Case of Merge Sort static void generateWorstCase ( int arr [] int l int r ) { if ( l < r ) { int m = l + ( r - l ) / 2 ; // create two auxiliary arrays int [] left = new int [ m - l + 1 ] ; int [] right = new int [ r - m ] ; // Store alternate array elements in left // and right subarray split ( arr left right l m r ); // Recurse first and second halves generateWorstCase ( left l m ); generateWorstCase ( right m + 1 r ); // join left and right subarray join ( arr left right l m r ); } } // driver program public static void main ( String [] args ) { // sorted array int arr [] = { 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 }; int n = arr . length ; System . out . println ( 'Sorted array is' ); System . out . println ( Arrays . toString ( arr )); // generate Worst Case of Merge Sort generateWorstCase ( arr 0 n - 1 ); System . out . println ( 'nInput array that will result in n' + 'worst case of merge sort is n' ); System . out . println ( Arrays . toString ( arr )); } } // Contributed by Pramod KumarC## Python program to generate Worst Case of Merge Sort # Function to join left and right subarray def join ( arr left right l m r ): i = 0 ; for i in range ( m - l + 1 ): arr [ i ] = left [ i ]; i += 1 ; for j in range ( r - m ): arr [ i + j ] = right [ j ]; # Function to store alternate elements in left # and right subarray def split ( arr left right l m r ): for i in range ( m - l + 1 ): left [ i ] = arr [ i * 2 ]; for i in range ( r - m ): right [ i ] = arr [ i * 2 + 1 ]; # Function to generate Worst Case of Merge Sort def generateWorstCase ( arr l r ): if ( l < r ): m = l + ( r - l ) // 2 ; # create two auxiliary arrays left = [ 0 for i in range ( m - l + 1 )]; right = [ 0 for i in range ( r - m )]; # Store alternate array elements in left # and right subarray split ( arr left right l m r ); # Recurse first and second halves generateWorstCase ( left l m ); generateWorstCase ( right m + 1 r ); # join left and right subarray join ( arr left right l m r ); # driver program if __name__ == '__main__' : # sorted array arr = [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ]; n = len ( arr ); print ( 'Sorted array is' ); print ( arr ); # generate Worst Case of Merge Sort generateWorstCase ( arr 0 n - 1 ); print ( ' n Input array that will result in n ' + 'worst case of merge sort is ' ); print ( arr ); # This code contributed by shikhasingrajputJavaScript// C# program to generate Worst Case of // Merge Sort using System ; class GFG { // Function to join left and right subarray static void join ( int [] arr int [] left int [] right int l int m int r ) { int i ; for ( i = 0 ; i <= m - l ; i ++ ) arr [ i ] = left [ i ]; for ( int j = 0 ; j < r - m ; j ++ ) arr [ i + j ] = right [ j ]; } // Function to store alternate elements in // left and right subarray static void split ( int [] arr int [] left int [] right int l int m int r ) { for ( int i = 0 ; i <= m - l ; i ++ ) left [ i ] = arr [ i * 2 ]; for ( int i = 0 ; i < r - m ; i ++ ) right [ i ] = arr [ i * 2 + 1 ]; } // Function to generate Worst Case of // Merge Sort static void generateWorstCase ( int [] arr int l int r ) { if ( l < r ) { int m = l + ( r - l ) / 2 ; // create two auxiliary arrays int [] left = new int [ m - l + 1 ]; int [] right = new int [ r - m ]; // Store alternate array elements // in left and right subarray split ( arr left right l m r ); // Recurse first and second halves generateWorstCase ( left l m ); generateWorstCase ( right m + 1 r ); // join left and right subarray join ( arr left right l m r ); } } // driver program public static void Main () { // sorted array int [] arr = { 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 }; int n = arr . Length ; Console . Write ( 'Sorted array isn' ); for ( int i = 0 ; i < n ; i ++ ) Console . Write ( arr [ i ] + ' ' ); // generate Worst Case of Merge Sort generateWorstCase ( arr 0 n - 1 ); Console . Write ( 'nInput array that will ' + 'result in n worst case of' + ' merge sort is n' ); for ( int i = 0 ; i < n ; i ++ ) Console . Write ( arr [ i ] + ' ' ); } } // This code is contributed by Smitha산출:
Sorted array is
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Input array that will result in worst
case of merge sort is
1 9 5 13 3 11 7 15 2 10 6 14 4 12 8 16시간 복잡성 : O (n logn)
보조 공간 : O (N)
참조 - 스택 오버플로
