Рубрики

Сортировка слиянием

Как и QuickSort , Merge Sort — это алгоритм « разделяй и властвуй» . Он разделяет входной массив на две половины, вызывает себя для двух половинок и затем объединяет две отсортированные половины. Функция merge () используется для объединения двух половинок. Слияние (arr, l, m, r) является ключевым процессом, который предполагает, что arr [l..m] и arr [m + 1..r] отсортированы и объединяет два отсортированных подмассива в один. Смотрите следующую реализацию C для деталей.

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = (l+r)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)

Следующая диаграмма из википедии показывает полный процесс сортировки слиянием для примера массива {38, 27, 43, 3, 9, 82, 10}. Если мы более внимательно посмотрим на диаграмму, то увидим, что массив рекурсивно разделен на две половины, пока размер не станет равным 1. Как только размер станет равным 1, процессы слияния вступают в действие и начинают объединять массивы обратно до тех пор, пока весь массив не станет слиты.

C / C ++

/ * C программа для сортировки слиянием * /
#include<stdlib.h>
#include<stdio.h>

  
// Объединяет два подмассива arr [].
// Первый подмассив - это arr [l..m]
// Второй подмассив - это arr [m + 1..r]

void merge(int arr[], int l, int m, int r)

{

    int i, j, k;

    int n1 = m - l + 1;

    int n2 =  r - m;

  

    / * создать временные массивы * /

    int L[n1], R[n2];

  

    / * Копировать данные во временные массивы L [] и R [] * /

    for (i = 0; i < n1; i++)

        L[i] = arr[l + i];

    for (j = 0; j < n2; j++)

        R[j] = arr[m + 1+ j];

  

    / * Объединить временные массивы обратно в arr [l..r] * /

    i = 0; // Начальный индекс первого подмассива

    j = 0; // Начальный индекс второго подмассива

    k = l; // Начальный индекс объединенного подмассива

    while (i < n1 && j < n2)

    {

        if (L[i] <= R[j])

        {

            arr[k] = L[i];

            i++;

        }

        else

        {

            arr[k] = R[j];

            j++;

        }

        k++;

    }

  

    / * Копировать оставшиеся элементы L [], если есть

       любые * /

    while (i < n1)

    {

        arr[k] = L[i];

        i++;

        k++;

    }

  

    / * Скопировать оставшиеся элементы R [], если есть

       любые * /

    while (j < n2)

    {

        arr[k] = R[j];

        j++;

        k++;

    }

}

  
/ * l - левый индекс, а r - правый индекс

   подмассив arr для сортировки * /

void mergeSort(int arr[], int l, int r)

{

    if (l < r)

    {

        // То же, что (l + r) / 2, но избегает переполнения для

        // большие л и ч

        int m = l+(r-l)/2;

  

        // Сортировка первой и второй половин

        mergeSort(arr, l, m);

        mergeSort(arr, m+1, r);

  

        merge(arr, l, m, r);

    }

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для печати массива * /

void printArray(int A[], int size)

{

    int i;

    for (i=0; i < size; i++)

        printf("%d ", A[i]);

    printf("\n");

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    int arr[] = {12, 11, 13, 5, 6, 7};

    int arr_size = sizeof(arr)/sizeof(arr[0]);

  

    printf("Given array is \n");

    printArray(arr, arr_size);

  

    mergeSort(arr, 0, arr_size - 1);

  

    printf("\nSorted array is \n");

    printArray(arr, arr_size);

    return 0;

}

Джава

/ * Java-программа для сортировки слиянием * /

class MergeSort

{

    // Объединяет два подмассива arr [].

    // Первый подмассив - это arr [l..m]

    // Второй подмассив - это arr [m + 1..r]

    void merge(int arr[], int l, int m, int r)

    {

        // Находим размеры двух подмассивов для объединения

        int n1 = m - l + 1;

        int n2 = r - m;

  

        / * Создать временные массивы * /

        int L[] = new int [n1];

        int R[] = new int [n2];

  

        / * Копировать данные во временные массивы * /

        for (int i=0; i<n1; ++i)

            L[i] = arr[l + i];

        for (int j=0; j<n2; ++j)

            R[j] = arr[m + 1+ j];

  

  

        / * Объединить временные массивы * /

  

        // Начальные индексы первого и второго подмассивов

        int i = 0, j = 0;

  

        // Начальный индекс объединенного массива subarry

        int k = l;

        while (i < n1 && j < n2)

        {

            if (L[i] <= R[j])

            {

                arr[k] = L[i];

                i++;

            }

            else

            {

                arr[k] = R[j];

                j++;

            }

            k++;

        }

  

        / * Копировать оставшиеся элементы L [], если есть * /

        while (i < n1)

        {

            arr[k] = L[i];

            i++;

            k++;

        }

  

        / * Копировать оставшиеся элементы R [], если есть * /

        while (j < n2)

        {

            arr[k] = R[j];

            j++;

            k++;

        }

    }

  

    // Основная функция, которая сортирует arr [l..r] используя

    // merge ()

    void sort(int arr[], int l, int r)

    {

        if (l < r)

        {

            // Найти среднюю точку

            int m = (l+r)/2;

  

            // Сортировка первой и второй половин

            sort(arr, l, m);

            sort(arr , m+1, r);

  

            // Объединяем отсортированные половинки

            merge(arr, l, m, r);

        }

    }

  

    / * Утилита для печати массива размером n * /

    static void printArray(int arr[])

    {

        int n = arr.length;

        for (int i=0; i<n; ++i)

            System.out.print(arr[i] + " ");

        System.out.println();

    }

  

    // Метод драйвера

    public static void main(String args[])

    {

        int arr[] = {12, 11, 13, 5, 6, 7};

  

        System.out.println("Given Array");

        printArray(arr);

  

        MergeSort ob = new MergeSort();

        ob.sort(arr, 0, arr.length-1);

  

        System.out.println("\nSorted array");

        printArray(arr);

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

python3

# Python программа для реализации MergeSort

def mergeSort(arr):

    if len(arr) >1:

        mid = len(arr)//2 # Нахождение середины массива

        L = arr[:mid] # Разделение элементов массива

        R = arr[mid:] # на 2 половинки

  

        mergeSort(L) # Сортировка первой половины

        mergeSort(R) # Сортировка второй половины

  

        i = j = k = 0

          

        # Копировать данные во временные массивы L [] и R []

        while i < len(L) and j < len(R):

            if L[i] < R[j]:

                arr[k] = L[i]

                i+=1

            else:

                arr[k] = R[j]

                j+=1

            k+=1

          

        # Проверка, оставлен ли какой-либо элемент

        while i < len(L):

            arr[k] = L[i]

            i+=1

            k+=1

          

        while j < len(R):

            arr[k] = R[j]

            j+=1

            k+=1

  
# Код для печати списка

def printList(arr):

    for i in range(len(arr)):        

        print(arr[i],end=" ")

    print()

  
# код драйвера для проверки вышеуказанного кода

if __name__ == '__main__':

    arr = [12, 11, 13, 5, 6, 7

    print ("Given array is", end="\n"

    printList(arr)

    mergeSort(arr)

    print("Sorted array is: ", end="\n")

    printList(arr)

  
# Этот код предоставлен Mayank Khanna

Выход:

Given array is
12 11 13 5 6 7

Sorted array is
5 6 7 11 12 13

Сложность времени: сортировка массивов на разных машинах. Сортировка слиянием является рекурсивным алгоритмом, а сложность по времени может быть выражена в виде следующего рекуррентного соотношения.
T (n) = 2T (n / 2) +
Вышеуказанное повторение может быть решено с использованием метода дерева повторений или метода Master. Это относится к случаю II мастер-метода и решение повторения ,
Временная сложность Merge Sort составляет во всех 3 случаях (худший, средний и лучший) сортировка слиянием всегда делит массив на две половины и требует линейного времени для объединения двух половин.

Вспомогательное пространство: O (n)

Алгоритмическая парадигма: разделяй и властвуй

Сортировка на месте: нет в типичной реализации

Стабильно: да

Приложения сортировки слиянием

  1. Сортировка слиянием полезна для сортировки связанных списков за время O (nLogn). В случае связанных списков случай отличается в основном из-за разницы в распределении памяти массивов и связанных списков. В отличие от массивов, узлы связанного списка могут не быть смежными в памяти. В отличие от массива, в связанный список мы можем вставлять элементы посередине в O (1) дополнительное пространство и O (1) время. Поэтому операция слияния сортировки слиянием может быть реализована без дополнительного места для связанных списков.

    В массивах мы можем осуществлять произвольный доступ, так как элементы непрерывны в памяти. Допустим, у нас есть целочисленный (4-байтовый) массив A, и пусть адрес A [0] будет равен x, чтобы получить доступ к A [i], мы можем напрямую получить доступ к памяти в (x + i * 4). В отличие от массивов, мы не можем делать произвольный доступ в связанном списке. Быстрая сортировка требует большого количества такого доступа. В связанном списке для доступа к i-му индексу мы должны перемещать каждый узел от головы до i-го узла, поскольку у нас нет непрерывного блока памяти. Поэтому накладные расходы возрастают для быстрой сортировки. Сортировка слиянием обращается к данным последовательно, и потребность в произвольном доступе низка.

  2. Проблема Инверсии
  3. Используется во внешней сортировке

Фотосъёмка:

Другие алгоритмы сортировки на GeeksforGeeks:
Трехсторонняя сортировка слиянием, сортировка выбора , сортировка по пузырям , сортировка по вставке, сортировка по слиянию , сортировка по куче , быстрая сортировка , сортировка по корням, сортировка по счету , сортировка по корзине , сортировка по оболочке , сортировка по гребне

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Сортировка слиянием

0.00 (0%) 0 votes