Wanneer zal het ergste geval van samenvoegen sorteren plaatsvinden?

Ik weet dat het slechtste geval op mergesort O(nlogn) is, hetzelfde als het gemiddelde geval.

Als de gegevens echter oplopend of aflopend zijn, resulteert dit in het minimum aantal vergelijkingen, en daarom wordt mergesort sneller dan willekeurige gegevens. Dus mijn vraag is: wat voor soort invoergegevens produceren het maximale aantal vergelijkingendat resulteert in een langzamere mergesort?

Het antwoord op dezevraag zegt:

Voor sommige sorteeralgoritmen (bijv. quicksort) is de beginvolgorde van de
elementen kunnen het aantal uit te voeren bewerkingen beïnvloeden. Het is echter
brengt geen verandering aan voor mergesort omdat het precies moet doen
toch hetzelfde aantal bewerkingen: recursief verdelen in kleine
arrays en voeg ze vervolgens weer samen, in totaal Θ(nlogn) tijd.

Dit is echter fout. Op het moment dat we twee subarrays hebben en we willen ze samenvoegen als de initiële gegevens zijn gesorteerd, hebben we alleen n/2 vergelijkingen. Dat zijn alle elementen van de eerste subarray met alleenhet eerste element van de tweede array. We kunnen echter meer bereiken dan dat. Ik ben op zoek naar die invoergegevens.

Antwoord 1, autoriteit 100%

In het slechtste geval van merge sort zal het merge sort maximaal aantal vergelijkingen moeten doen.

Dus ik zal proberen de worst case bottom-up op te bouwen:

1. Stel dat de array in de laatste stap na het sorteren {0,1,2,3,4,5,6,7}

is

2. In het ergste geval moet de array vóór deze stap {0,2,4,6,1,3,5,7}zijn, omdat hier links subarray={0,2,4,6}en rechter subarray={1,3,5,7}resulteren in maximale vergelijkingen.(Alternatieve elementen opslaan in linker en rechter subarray)

   Reden:elk element van de array wordt minstens één keer vergeleken.

3. Dezelfde bovenstaande logica toepassen voor linker- en rechtersubarray voor eerdere stappen: Voor array {0,2,4,6}is het ergste geval als de vorige array {0,4}en {2,6}en voor array {1,3,5,7}is het slechtste geval voor {1,5}en {3,7}.

4. Toepassen nu hetzelfde voor eerdere step-arrays:
   In het ergste geval: {0,4}moet {4,0}, {2,6}zijn moet {6,2}zijn,{1,5}moet {5,1}{3,7}moet {7,3}zijn. Als je goed kijkt, is deze stap niet nodig, want als de grootte van set/array 2 is, wordt elk element minstens één keer vergeleken, zelfs als array van grootte 2 is gesorteerd.

Nu top-down en de situatie analyseren

Applying Merge Sort using Divide and Conquer
Input array arr[] = [4,0,6,2,5,1,7,3]
                           /  \
                          /    \
                  [4,0,6,2] and [5,1,7,3]
                     / \           / \
                    /   \         /   \
                 [4,0] [6,2]    [5,1] [7,3]       Every pair of 2 will be compared atleast once therefore maximum comparison here
                   |     |        |     |
                   |     |        |     |
                 [0,4] [2,6]    [1,5] [3,7]      Maximum Comparison:Every pair of set is used in comparison     
                   \     /        \     /                        
                    \   /          \   /
                 [0,2,4,6]      [1,3,5,7]        Maximum comparison again: Every pair of set compared
                      \             /
                       \           / 
                     [0,1,2,3,4,5,6,7]          

Nu kunt u dezelfde logica toepassen op elke array met de grootte n

Hieronder staat het programma dat de bovenstaande logica implementeert.

Opmerking: Het onderstaande programma is niet alleen geldig voor machten van 2. Het is een algemene methode om het slechtste geval te bieden voor elke array van grootte n. U kunt zelf verschillende arrays proberen om in te voeren.

class MergeWorstCase
{
    public static void print(int arr[])
    {
        System.out.println();
        for(int i=0;i<arr.length;i++)
            System.out.print(arr[i]+" ");
        System.out.println();
    }
    public static void merge(int[] arr, int[] left, int[] right) {
        int i,j;
        for(i=0;i<left.length;i++)
                arr[i]=left[i];
        for(j=0;j<right.length;j++,i++)
                arr[i]=right[j];
    }
    //Pass a sorted array here
    public static void seperate(int[] arr) { 
            if(arr.length<=1)
                return;
            if(arr.length==2)
            {
                int swap=arr[0];
                arr[0]=arr[1];
                arr[1]=swap;
                return;
            }
        int i,j;
        int m = (arr.length + 1) / 2;
        int left[] = new int[m];
        int right[] = new int[arr.length-m];
        for(i=0,j=0;i<arr.length;i=i+2,j++) //Storing alternate elements in left subarray
            left[j]=arr[i];
        for(i=1,j=0;i<arr.length;i=i+2,j++) //Storing alternate elements in right subarray
            right[j]=arr[i];
        seperate(left);
        seperate(right);
        merge(arr, left, right);
    }
    public static void main(String args[])
    {
        int arr1[]={0,1,2,3,4,5,6,7};
        seperate(arr1);
        System.out.print("For array 1:");
        print(arr1);
        int arr2[]={0,1,2,3,4,5,6,7,8};
        seperate(arr2);
        System.out.print("For array 2:");
        print(arr2);            
    }
}

Uitgang:

For array 1:
4 0 6 2 5 1 7 3 
For array 2:
8 0 4 6 2 5 1 7 3 

Antwoord 2, Autoriteit 7%

algoritme

Een nette algoritme Een van mijn professoren gaf me opgelost dit met behulp van een tegenovergestelde aanpak. In plaats van de initiële array in kleinere en kleinere blokken te splitsen, kunt u beginnen met een basiskoffer en een recursief patroon volgen.

Basiscase is [1] en [2, 1], die de voorbeelden zijn voor worstcase-arrays van grootte 1en 2. Hieruit bouw je arrays voor 3en 4als volgt.

1. Neem twee arrays met formaten nen m, zodanig dat n + m = x, waarbij x de grootte is die u kijkt voor
2. Combineer ze, met de reeks kleinere maat aan de bovenkant
3. Dubbel elk element in de bovenste array
4. Dubbel elk element en trek 1 af van de onderste array

Gebruik dit algoritme, hier is de reeks stappen voor arrays van maat 3EN 4.

Voorbeelden

Maat 3

1. Neem [1] + [2, 1]
2. die u krijgt [1 | 2, 1]
3. [2 | 2, 1]
4. [2 | 3, 1] -> [2, 3, 1]

Maat 4

1. Neem [2, 1] + [2, 1]
2. u krijgt [2, 1 | 2, 1]
3. [4, 2 | 2, 1]
4. [4, 2 | 3, 1] -> [4, 2, 3, 1]

Maat 7

1. Neem [2, 3, 1] + [4, 2, 3, 1]
2. Je krijgt [2, 3, 1 | 4, 2, 3, 1]
3. [4, 6, 2 | 4, 2, 3, 1]
4. [4, 6, 2 | 7, 3, 5, 1] -> [4, 6, 2, 7, 3, 5, 1]

Het is gemakkelijk om te zien hoe u deze aanpak kunt volgen en eenvoudig kunt opbouwen tot enorme arraygroottes.

Programma

Hier is een python-functie die dit algoritme implementeert.

import math
def worstCaseArrayOfSize(n):
    if n == 1:
        return [1]
    else:
        top = worstCaseArrayOfSize(int(math.floor(float(n) / 2)))
        bottom = worstCaseArrayOfSize(int(math.ceil(float(n) / 2)))
        return map(lambda x: x * 2, top) + map(lambda x: x * 2 - 1, bottom)