Когда произойдет худший случай Merge Sort?

Ответ 1

Худший случай сортировки слияния будет тем, где сортировка слияния должна будет выполнять максимальное количество сравнений.

Итак, я постараюсь создать худший случай снизу вверх:

• Предположим, что массив на последнем шаге после сортировки {0,1,2,3,4,5,6,7}

• В худшем случае массив до этого шага должен быть {0,2,4,6,1,3,5,7}, потому что здесь left subarray = {0,2,4,6}, а правый subarray = {1,3,5,7} приведет к максимальным сравнениям (сохранение альтернативных элементов в левом и правом подмассивах)

  Причина: Каждый элемент массива будет сравниваться по крайней мере один раз.

• Применение такой же логики выше для левого и правого подмассивов для предыдущих шагов: для массива {0,2,4,6} наихудший случай будет, если предыдущий массив равен {0,4} и {2,6}, а для массива {1,3,5,7} худший case будет для {1,5} и {3,7}.

• Теперь применим то же самое для предыдущих шаговых массивов: Для худших случаев: {0,4} должен быть {4,0}, {2,6} должен быть {6,2}, {1,5} должен быть {5,1} {3,7} должен быть {7,3}. Хорошо, если вы посмотрите, что этот шаг не нужен, потому что если размер набора/массива равен 2, то каждый элемент будет сравниваться по крайней мере один раз, даже если отсортирован массив размером 2.

Теперь переходим вниз и анализируем ситуацию

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]          

Теперь вы можете применить ту же логику для любого массива размера n

Ниже приведена программа, которая реализует вышеуказанную логику.

Примечание: приведенная ниже программа недействительна только для степеней 2. Это обобщенный метод, обеспечивающий наихудший случай для любого массива размера n. Вы можете попробовать разные массивы для ввода самостоятельно.

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

Выход:

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

Ответ 2

Алгоритм

Чистый алгоритм, который дал мне один из моих профессоров, решает это, используя противоположный подход. Вместо того, чтобы разбивать начальный массив на меньшие и меньшие блоки, вы можете начать с базового случая и следовать рекурсивному шаблону.

Базовый регистр - это [1] и [2, 1], которые являются примерами для массивов худших случаев размером 1 и 2. Из этого вы создаете массивы для 3 и 4 следующим образом.

• Возьмите два массива размеров n и m, таких, что n + m = x, где x - размер, который вы ищете
• Объедините их с массивом меньшего размера, расположенным вверху
• Двойной элемент в верхнем массиве
• Двойной элемент и вычитаем 1 из нижнего массива

Используя этот алгоритм, здесь приведен ряд шагов для массивов размером 3 и 4.

Примеры

Размер 3

• Возьмите [1] + [2, 1]
• Вы получаете [1 | 2, 1]
• [2 | 2, 1]
• [2 | 3, 1] -> [2, 3, 1]

Размер 4

• Возьмите [2, 1] + [2, 1]
• Вы получаете [2, 1 | 2, 1]
• [4, 2 | 2, 1]
• [4, 2 | 3, 1] -> [4, 2, 3, 1]

Размер 7

• Возьмите [2, 3, 1] + [4, 2, 3, 1]
• Вы получаете [2, 3, 1 | 4, 2, 3, 1]
• [4, 6, 2 | 4, 2, 3, 1]
• [4, 6, 2 | 7, 3, 5, 1] -> [4, 6, 2, 7, 3, 5, 1]

Легко понять, как вы можете использовать этот подход и легко создавать до огромных размеров массива.

Программа

Здесь используется функция python, которая реализует этот алгоритм.

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)