Znajdź permutację, która powoduje najgorszy przypadek sortowania
Biorąc pod uwagę zestaw elementów, które permutacja tych elementów spowodowałaby najgorszy przypadek sortowania.
Asymptotycznie scalanie zawsze wymaga czasu O (n log n), ale przypadki wymagające większej liczby porównań na ogół wymagają więcej czasu w praktyce. Zasadniczo musimy znaleźć permutację elementów wejściowych, które doprowadziłyby do maksymalnej liczby porównań po sortowaniu przy użyciu typowego algorytmu sortowania scalania.
Przykład:
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.Teraz, jak uzyskać najgorsze dane wejściowe do sortowania sortowania dla zestawu wejściowego?
Pozwala nam zbudować tablicę w sposób
Niech posortowana tablica będzie {12345678}.W celu wygenerowania najgorszego przypadku sortowania sortowania operacji scalania, która spowodowała powyższą tablicę, powinna skutkować maksymalnym porównań. Aby to zrobić, lewa i prawowa podatak zaangażowany w operację scalania powinien przechowywać alternatywne elementy posortowanej tablicy. tj. lewy pod-podorządek powinien wynosić {1357}, a prawy podarka powinna wynosić {2468}. Teraz każdy element tablicy zostanie porównany raz, co spowoduje maksymalne porównania. Stosujemy również tę samą logikę dla lewej i prawej podrzędnej. W przypadku tablicy {1357} najgorszym przypadkiem będzie, gdy jego lewa i prawa podrzędna jest odpowiednio {15} i {37} oraz dla tablicy {2468} najgorszy przypadek wystąpi dla {24} i {68}.
Kompletny algorytm -
GenerateWorstCase (ARR [])
- Utwórz dwie pomocy pomocy lewej i prawej i przechowuj w nich alternatywne elementy tablicy.
- Call GenerateWorScase dla lewej podbazu: GenerateWorstCase (po lewej)
- Call GenerateWorScase dla prawej podarunki: GenerateWorstCase (po prawej)
- Skopiuj wszystkie elementy lewej i prawej podgrzewu z powrotem do oryginalnej tablicy.
Poniżej znajduje się wdrożenie pomysłu
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 SmithaWyjście:
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 16Złożoność czasu: o (n logn)
Przestrzeń pomocnicza: o (n)
Odniesienia - Przepełnienie stosu
