Raskite permutaciją, kuri sukelia blogiausią susijungimo atvejį
Atsižvelgiant į elementų rinkinį, kuris nustato, kuris šių elementų permutacija sukeltų blogiausiu atveju sujungimo rūšis.
Asimptotiškai susijungimo rūšis visada užtrunka (n log n), tačiau atvejai, kuriems reikia daugiau palyginimų, paprastai reikalauja daugiau laiko praktiškai. Iš esmės mums reikia rasti įvesties elementų permutaciją, dėl kurios rūšiuojant naudojant tipišką sujungimo rūšiavimo algoritmą, būtų pasiektas maksimalus palyginimų skaičius.
Pavyzdys:
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.Dabar kaip gauti blogiausio atvejo įvesties įvesties įvesties įvesties rinkinį?
Leidžia mums pabandyti sukurti masyvą iš apačios į viršų
Tegul surūšiuotas masyvas yra {12345678}.Norint sugeneruoti blogiausią sujungimo atvejį, rūšiuoti sujungimo operaciją, dėl kurios aukščiau išdėstytas masyvas turėtų būti maksimalus palyginimas. Norint tai padaryti, kairiajame ir dešiniajame poskyryje, dalyvaujančiame sujungimo operacijoje, turėtų būti išsaugoti alternatyvūs rūšiuoto masyvo elementai. y., kairiojo pobūdis turėtų būti {1357}, o dešiniojo poskyris turėtų būti {2468}. Dabar kiekvienas masyvo elementas bus lyginamas vieną kartą ir tai bus palyginami maksimaliai palyginimai. Tą pačią logiką taikome ir kairiajam ir dešiniajam poskyriui. Masyvas {1357} Blogiausias atvejis bus tada, kai jo kairėje ir dešinėje yra atitinkamai {15} ir {37}, o masyvui {2468}-blogiausias atvejis įvyks {24} ir {68}.
Visas algoritmas -
Generateworstcase (arr [])
- Sukurkite du pagalbinius masyvus iš kairės ir dešinės ir saugokite alternatyvius masyvo elementus.
- „Call GenerateWorstcase“, skirtas kairiajam „Subarray“: „GenerateWorstCase“ (kairėje)
- „Call GenerateWorstcase“, skirtas dešiniajam subarracijai: generuoti „WorldCase“ (dešinėje)
- Nukopijuokite visus kairiojo ir dešiniojo poskyrio elementus atgal į originalų masyvą.
Žemiau yra idėjos įgyvendinimas
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 SmithaIšvestis:
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 16Laiko sudėtingumas: o (n logn)
Pagalbinė erdvė: o (n)
Nuorodos - Krūvos perpildymas
