Сортировка слиянием (Merge Sort) в Python

Spread the love


Введение

Сортировка слиянием (Merge Sort) – один из самых известных алгоритмов сортировки. Если вы изучаете информатику, Merge Sort вместе с Quick Sort, вероятно, является первым эффективным алгоритмом сортировки общего назначения, о котором вы слышали. Также классический пример алгоритма «разделяй и властвуй» (divide-and-conquer).

Merge Sort

Алгоритм сортировки слиянием работает так:

Исходный массив делится на две примерно равные части. Если массив имеет нечетное количество элементов, одна из этих «половин» на один элемент больше, чем другая.

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

Затем вы объединяете пары одноэлементных массивов в двухэлементные массивы, сохраняя их в процессе. Затем эти отсортированные пары объединяются в четырехэлементные массивы и так далее до тех пор, пока не будет получен исходный отсортированный массив.

Вот визуализация сортировки слиянием:

Как вы можете видеть, тот факт, что массив не может быть разделен на равные половины, не является проблемой, 1 просто «ждет», пока не начнется сортировка.

Существует два основных способа реализации алгоритма сортировки слиянием, один из которых использует подход сверху вниз, как в примере выше, и именно так чаще всего используется.

Другой подход, то есть восходящий, работает в противоположном направлении, без рекурсии (работает итеративно) – если наш массив имеет N элементов, мы делим его на N подмассивов одного элемента и сортируем пары смежных одноэлементных массивов, затем сортируем соседние пары двухэлементных массивов и т. д.

Примечание: подход снизу вверх обеспечивает интересную оптимизацию. Но мы будем реализовывать нисходящий подход, так как это более простые и интуитивно понятные пары с тем фактом, что между ними нет реальной разницы во временной сложности без особых оптимизаций.

Основная часть обоих этих подходов заключается в том, как мы объединяем (merge) два меньших массива в больший массив. Это сделано довольно интуитивно, скажем, мы рассмотрим последний шаг в нашем предыдущем примере. У нас есть массивы:

  • A: 4 7 9 10
  • B: 1 3 6
  • sorted: empty

Первое, что мы сделаем, это посмотрим на первый элемент обоих массивов. Мы находим тот, который меньше, в нашем случае это 1, так что это первый элемент нашего отсортированного массива, и мы продвигаемся вперед в массиве B:

  • A:  4 7 9 10
  • B: 1 3 6
  • sorted: 1

Затем мы смотрим на следующую пару элементов 4 и 3; 3 меньше, поэтому мы помещаем его в наш отсортированный массив и перемещаемся вперед в массиве B. Конечно, мы не перемещаемся вперед в массиве A, и мы сохраняем наш указатель на 3 для будущих сравнений:

  • A: 4 7 9 10
  • B: 1 3 6
  • sorted: 1 3

Используя ту же логику, мы перемещаемся по остальным и получаем массив {1, 3, 4, 6, 7, 9, 10}.

Возможны два особых случая:

  • Оба подмассива имеют одинаковый элемент. Мы можем двигаться вперед в любом из них и добавить элемент в отсортированный массив. Мы можем технически продвинуться вперед в обоих массивах и добавить оба элемента в отсортированный массив, но это потребует особого поведения, когда мы встретим одинаковые элементы в обоих массивах.
  • Мы “исчерпали” элементы в одном подмассиве. Например, у нас есть массив с {1, 2, 3} и массив с {11, 12, 13}. Ясно, что мы пройдемся по всем элементам первого массива, не продвигаясь вперед ни разу во втором. Всякий раз, когда у нас заканчиваются элементы в подмассиве, мы просто добавляем элементы второго за другим.

Имейте в виду, что мы можем сортировать по своему усмотрению – этот пример сортирует целые числа в порядке возрастания, но мы можем так же легко сортировать в порядке убывания или сортировать пользовательские объекты.

Реализация

Мы будем реализовывать сортировку слиянием на массивах целых чисел (обычно используемых для представления сортировки).

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

Сортировка массивов

Начнем с простой части. Основная идея алгоритма состоит в том, чтобы разделить (под) массивы пополам и отсортировать их рекурсивно. Мы будем продолжать делать это как можно больше, то есть до тех пор, пока не получим подмассивы, которые имеют только один элемент:

import operator
def merge_sort(L, compare=operator.lt):
    if len(L) < 2:
        return L[:]
    else:
        middle = int(len(L) / 2)
        left = merge_sort(L[:middle], compare)
        right = merge_sort(L[middle:], compare)
        return merge(left, right, compare)

Последним вызовом метода merge мы гарантируем, что все деления произойдут до того, как мы начнем сортировку.

Создадим функцию merge():

 
def merge(left, right, compare):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if compare(left[i], right[j]):
            result. append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while i < len(left):
        result.append(left[i])
        i += 1
    while j < len(right):
        result.append(right[j])
        j += 1
    return result

Теперь давайте проверим нашу программу:

 
array = [78, 41, 4, 27, 3, 27, 8, 39, 19, 34, 6, 41, 13, 52, 16]
merge_sort(array)

И результат:

[3, 4, 6, 8, 13, 16, 19, 27, 27, 34, 39, 41, 41, 52, 78]

Заключение

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

Одним из основных недостатков является дополнительная память, которую сортировка слиянием использует для хранения временных копий массивов перед их объединением. Тем не менее, Merge Sort является отличным, интуитивно понятным примером для ознакомления будущих инженеров-программистов с подходом «разделяй и властвуй».

Источники используемые для написания статьи:  
Olivera Popović – Merge Sort in Python
https://stackoverflow.com/questions/18761766/mergesort-with-python

Была ли вам полезна эта статья?

[36 / 3.2]


Spread the love

Алгоритм сортировки слиянием — шпаргалка для начинающих

0 ∞ 2

Сортировка слиянием (merge sort) — один из самых популярных алгоритмов сортировки, который помогает освоить навыки составления рекурсивных алгоритмов.

  • Стратегия «разделяй и властвуй»
  • «Разделяй»
  • «Властвуй»
  • Объединение
  • Алгоритм MergeSort
  • Этап слияния
  • Написание кода для алгоритма слияния
  • Пошаговое пояснение функции слияния
    • Шаг 1: Создать повторяющиеся копии подмассивов для сортировки
    • Шаг 2: Сохранить текущий индекс подмассивов и основной массив merge sort C
    • Шаг 3: Пока не будет достигнут конец L или M, выбираем те, что больше среди элементов из L и M, и помещаем их в нужной позиции в A[p..r]
    • Шаг 4: Когда заканчиваются элементы в L или M, выбираем оставшиеся элементы и помещаем в A[p..r]

Применяя стратегию «разделяй и властвуй», мы делим задачу на подзадачи. Когда готово решение каждой подзадачи, их результаты объединяются, чтобы решить основную.

Предположим, нужно отсортировать массив A. Подзадачей будет сортировка подраздела этого массива, начиная с индекса p и заканчивая индексом r, обозначенного как A[p..r].

Если q — это точка на полпути между p и r, то подмассив A [p.

. r] можно разделить на два массива: A [p.. q] и A [q + 1, r].

На этапе «властвуй» сортируем оба подмассива A[p..q] и A[q+1, r]. Если мы еще не достигли базового случая, снова разделяем эти подмассивы и сортируем.

Если этап «завоевания» достигает базового, и для массива A[p..r] мы получаем два отсортированных подмассива A[p..q] и A[q+1, r], объединяем их результаты, создавая отсортированный массив A[p..r] из двух отсортированных A[p..q] и A[q+1, r]

В merge sort алгоритме одноименная функция делит массив на две половины пока не будет достигнут этап, где p == r.

После этого начинает действовать функция слияния. Она соединяет отсортированные массивы в более крупные пока не будет объединен весь массив.

MergeSort(A, p, r)
    If p > r 
        return;
    q = (p+r)/2;
    mergeSort(A, p, q)
    mergeSort(A, q+1, r)
    merge(A, p, q, r)

Чтобы отсортировать весь массив, нужно вызвать MergeSort(A, 0, length(A)-1).

Как показано на рисунке, алгоритм сортировки слиянием рекурсивно делит массив пополам пока не будет достигнут базовый случай. Затем функция слияния собирает отсортированные подмассивы и объединяет их, чтобы отсортировать весь массив.

Наиболее важной частью алгоритма сортировки слиянием является этап слияния. Это решение простой задачи слияния двух отсортированных списков (массивов) для построения одного большого отсортированного.

Алгоритм merge sort C поддерживает три указателя: по одному для каждого из двух массивов, и один для текущего индекса окончательного отсортированного массива.

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

Заметное различие между этапом слияния, описанным выше, и тем, который используется для merge sort, состоит в том, что функция слияния выполняется только для последовательных подмассивов. Вот почему нужен только массив, первая позиция, последний индекс первого подмассива (можно вычислить первый индекс второго подмассива) и последний индекс второго подмассива.

Наша задача состоит в объединении двух подмассивов A[p..q] и A[q+1..r], чтобы создать отсортированный массив A[p..r]. Таким образом, входными данными функции являются A, p, q и r.

Функция слияния работает следующим образом:

  1. Создает копии подмассивов L <- A[p..q] и M <- A[q+1..r].
  2. Создает три указателя i, j и k:
  • i сохраняет текущий индекс L, начиная с 1;
  • j сохраняет текущий индекс M, начиная с 1;
  • k сохраняет текущий индекс A[p..q], начиная с p.
  1. Пока не будет достигнут конец L или M, выбираем те, что больше среди элементов из L и M и помещаем их в нужной позиции в A[p..q]
  2. Когда заканчиваются элементы в L или M, выбираем оставшиеся элементы и помещаем в A[p..q]

В коде реализации merge sort алгоритма это будет выглядеть следующим образом:

void merge(int A[], int p, int q, int r)
{
    /* Создать L <- A[p..q] and M <- A[q+1..r] */
    int n1 = q - p + 1;
    int n2 =  r - q;
 
    int L[n1], M[n2];
    for (i = 0; i < n1; i++)
        L[i] = A[p + i];
    for (j = 0; j < n2; j++)
        M[j] = A[q + 1 + j];
    
    /* Сохранить текущий индекс подмассивов и основной массив */
    int i, j, k;
    i = 0; 
    j = 0; 
    k = p; 
    /*Пока не будет достигнут конец L или M, выбираем те, что больше среди элементов из L и M, и помещаем их в нужной позиции в A[p.
 
 .r] */
    while (i < n1 && j < n2)
    {
        if (L[i] <= M[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = M[j];
            j++;
        }
        k++;
    }
 
    /* Когда заканчиваются элементы в L или M, выбираем оставшиеся элементы и помещаем в A[p..r] */
    while (i < n1)
    {
        A[k] = L[i];
        i++;
        k++;
    }
 
    while (j < n2)
    {
        A[k] = M[j];
        j++;
        k++;
    }
}

Рассмотрим пример merge sort, который покажет, как это все работает:

Массив A[0..8] содержит два отсортированных подмассива A[1..5] и A[6..7]. Рассмотрим, как функция слияния объединяет два массива.

void merge(int A[], int p = 1, int q = 4, int 6)
{
/* Создать L <- A[p..q] and M <- A[q+1..r] */
    n1 = 4 - 1 + 1 = 4;
    n2 =  6 - 4 = 2;
 
    int L[4], M[2];
    for (i = 0; i < 4; i++)
        L[i] = A[p + i];
    /* L[0,1,2,3] = A[1,2,3,4] = [1,5,10,12] */
    for (j = 0; j < 2; j++)
        M[j] = A[q + 1 + j];
    /* M[0,1,2,3] = A[5,6] = [6,9]
int i, j, k;
    i = 0; 
    j = 0; 
    k = p;
while (i < n1 && j < n2) { 
        if (L[i] <= M[j]) { 
            A[k] = L[i]; i++; 
        } 
        else { 
            A[k] = M[j]; 
            j++; 
        } 
        k++; 
    }
/* Выходим из предыдущего цикла, поскольку i < n1 не поддерживается */  
    while (i < n1)
    {
        A[k] = L[i];
        i++;
        k++;
    }
/* Выходим из предыдущего цикла, поскольку i < n1 не поддерживается */  
    while (i < n1)
    {
        A[k] = L[i];
        i++;
        k++;
    }

В примере merge sort алгоритма этот шаг необходим, если размер M был больше L.

В конце функции слияния подмассив A[p..r] является отсортированным.

СМСергей Марочканичавтор статьи «Merge Sort Algorithm»

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

Объяснение сортировки слиянием: руководство по алгоритмам для специалистов по данным

Специалисты по данным ежедневно имеют дело с алгоритмами. Однако дисциплина науки о данных в целом превратилась в роль, не связанную с реализацией сложных алгоритмов. Тем не менее, практикующие специалисты могут извлечь выгоду из понимания и набора алгоритмов.

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

Хотя сортировка слиянием не считается сложной, понимание этого алгоритма поможет вам понять, какие факторы следует учитывать при выборе наиболее эффективного алгоритма для выполнения задач, связанных с данными. Созданный в 1945 году, Джон фон Нейман разработал алгоритм сортировки слиянием, используя подход «разделяй и властвуй».

Разделяй и властвуй

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

Другими словами, функция многократно вызывает сама себя.

Рисунок 1. Наглядная иллюстрация рекурсии — изображение автора .

Алгоритмы «разделяй и властвуй» (типом которых является сортировка слиянием) используют рекурсию в своем подходе к решению конкретных задач. Алгоритмы «разделяй и властвуй» разбивают сложные проблемы на более мелкие части, где определенное решение рекурсивно применяется к каждой части. Затем каждая подчасть решается отдельно, а решения объединяются для решения исходной задачи.

Подход «разделяй и властвуй» к разработке алгоритмов сочетает в себе три основных элемента:

  • Разложение большой проблемы на более мелкие подзадачи. (Разделить)
  • Рекурсивное использование функций для решения каждой из более мелких подзадач. (Завоевать)
  • Окончательное решение представляет собой композицию решения меньших подзадач более крупной проблемы. (Комбайн)

Другие алгоритмы используют парадигму «разделяй и властвуй», например, быстрая сортировка, двоичный поиск и алгоритм Штрассена.

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

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

Затем проводится сравнение меньших половин, и результаты объединяются для формирования окончательного отсортированного списка.

Этапы и реализация

Реализация алгоритма сортировки слиянием представляет собой трехэтапную процедуру. Разделяй, властвуй и объединяй.

Разделяющий компонент подхода «разделяй и властвуй» — это первый шаг. Этот начальный шаг делит общий список на две меньшие половины. Затем списки разбиваются до тех пор, пока их больше нельзя будет разделить, оставляя только один элемент элемента в каждом разделенном пополам списке.

Рекурсивный цикл во второй фазе сортировки слиянием связан с сортировкой элементов списка в определенном порядке. Для этого сценария исходный массив сортируется в порядке возрастания.

На следующем рисунке показаны этапы деления, сравнения и объединения, используемые в алгоритме сортировки слиянием.

Рис. 2. Иллюстрация компонента «Разделить» алгоритма сортировки слиянием — изображение автора.
Рисунок 3. Покоряйте и комбинируйте компоненты — изображение автора.

Чтобы реализовать это самостоятельно:

  • Создайте функцию с именем merge_sort, которая принимает в качестве аргумента список целых чисел. Все следующие инструкции относятся к этой функции.
  • Начните с разделения списка на две части. Запишите начальную длину списка.
  • Убедитесь, что записанная длина равна 1. Если условие оценивается как истинное, верните список, так как это означает, что в списке есть только один элемент. Поэтому нет необходимости делить список.
  • Получить среднюю точку для списка с количеством элементов больше 1. При использовании языка Python // выполняет деление без остатка. Он округляет результат деления до ближайшего целого числа. Это также известно как деление пола.
  • Используя среднюю точку в качестве ориентира, разделите список на две части. Это разделяющий аспект парадигмы алгоритма «разделяй и властвуй».
  • На этом шаге используется рекурсия, чтобы упростить разделение списков на компоненты, разделенные пополам. Переменные ‘left_half’ и ‘right_half’ назначаются для вызова функции ‘ merge_sort’ , принимая две половины исходного списка в качестве параметров.
  • Функция ‘ merge_sort ’ возвращает вызов функции, которая объединяет два списка, чтобы вернуть один объединенный отсортированный список.
 def merge_sort (список: [int]):
    list_length = длина (список)
    
    если длина_списка == 1:
        список возврата
    
    mid_point = длина_списка // 2
    
    левая_половина = сортировка_слияния (список [: середина_точки])
    right_half = merge_sort (список [mid_point:])
    
    вернуть слияние (левая_половина, правая_половина)
  • Создайте функцию «объединения» , которая принимает в качестве аргументов два списка целых чисел. Эта функция содержит аспекты завоевания и объединения парадигмы алгоритма «разделяй и властвуй». Все последующие шаги выполняются в теле этой функции.
  • Назначить пустой список переменной output, которая содержит отсортированные целые числа.
  • Указатели ‘i’ и ‘j’ используются для индексации левого и правого списков соответственно.
  • В цикле while происходит сравнение элементов левого и правого списков. После каждого сравнения выходной список заполняется двумя сравниваемыми элементами. Указатель списка добавляемого элемента увеличивается.
  • Оставшиеся элементы для добавления в отсортированный список — это элементы, полученные от текущего значения указателя до конца соответствующего списка.
 слияние по определению (слева, справа):
    вывод = []
    я = j = 0
    
    в то время как (i < len (слева) и j < len (справа)):
        если слева[i] < справа[j]:
            output.append (слева [i])
            я +=1
        еще:
            output.append (справа [j])
            j +=1
    output.extend (слева [i:])
    output.extend (справа [j:])
    
    возвратный вывод
    
unsorted_list = [2, 4, 1, 5, 7, 2, 6, 1, 1, 6, 4, 10, 33, 5, 7, 23]
отсортированный_список = слияние_сортировка (несортированный_список)
печать (несортированный_список)
печать (отсортированный_список)

Производительность и сложность

Нотация Big O — это стандарт для определения и организации производительности алгоритмов с точки зрения их требований к пространству и времени выполнения.

Временная сложность алгоритма сортировки слиянием одинакова для лучшего, худшего и среднего сценариев. Для списка размера n ожидаемое количество шагов, минимальное количество шагов и максимальное количество шагов для завершения алгоритма сортировки слиянием одинаковы.

Как отмечалось ранее в этой статье, алгоритм сортировки слиянием состоит из трех шагов: разделяй, властвуй и объединяй. Шаг «деления» включает в себя вычисление средней точки списка, которое, независимо от размера списка, занимает один рабочий шаг. Поэтому обозначение для этой операции обозначается как О(1) .

Шаг «завоевания» включает в себя деление и рекурсивное решение подмассивов — это обозначение log n. Шаг «объединения» состоит из объединения результатов в окончательный список; время выполнения этой операции зависит от размера списка и обозначается как O(n) .

Обозначение сортировки слиянием для средней, наилучшей и наихудшей временной сложности: log n * n * O(1) . В нотации Big O младшие члены и константы незначительны, что означает, что окончательное обозначение для алгоритма сортировки слиянием равно 9.0106 O(n log n) . Подробный анализ алгоритма сортировки слиянием см. в этой статье.

Оценка

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

Основные выводы

В этой статье описывается метод сортировки слиянием с разбивкой на составляющие его операции и пошаговые процессы.

Алгоритм сортировки слиянием широко используется, и интуиция и реализация этого алгоритма довольно просты по сравнению с другими алгоритмами сортировки. Эта статья включает этап реализации алгоритма сортировки слиянием в Python.

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

  • При работе с большими наборами данных используйте алгоритм сортировки слиянием. Сортировка слиянием плохо работает с небольшими массивами по сравнению с другими алгоритмами сортировки.
  • Элементы в связанном списке имеют ссылку на следующий элемент в списке. Это означает, что в операции алгоритма сортировки слиянием указатели можно модифицировать, что делает сравнение и вставку элементов постоянной временной и пространственной сложностью.
  • Иметь некоторую уверенность в том, что массив не отсортирован. Сортировка слиянием будет выполнять свои операции даже с отсортированными массивами, что является пустой тратой вычислительных ресурсов.
  • Используйте сортировку слиянием, если важна стабильность данных. Стабильная сортировка предполагает сохранение порядка идентичных значений в массиве. По сравнению с несортированными входными данными порядок идентичных значений в массиве при стабильной сортировке сохраняется на том же месте в отсортированном выходе.

Какова временная сложность сортировки слиянием?

Какова временная сложность сортировки слиянием?

Какова временная сложность сортировки слиянием?

share-outline Решение проблем DSA для интервью с использованием Java Решение для интервью с использованием Java

Jitender Punia

Бесплатно

Начать обучение

Сортировка слиянием — это простой в применении алгоритм сортировки, временная сложность которого составляет O(n∗logn)O(n * logn)O(n∗logn) для всех условия (лучший случай, худший случай и средний случай). Этот алгоритм основан на стратегии «разделяй и властвуй».

Алгоритм сортировки постоянно разбивает список на несколько подсписков, пока в каждом подсписке не останется только один элемент. Затем он объединяет эти подсписки в отсортированный список.

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

Сортировка слиянием, считающаяся наиболее эффективным алгоритмом сортировки, работает по принципу « Разделяй и властвуй ».

Алгоритм можно разделить на три части:

  1. Разделить - Это начальная стадия, где средняя точка массива находится с помощью mid=start+(end-start)/2mid=start+(end-start)/2mid=start+(end-start)/2
  2. Conquer — на этом этапе массив делится на подмассивы с использованием вычисленной средней точки. Процесс рекурсивно повторяется до тех пор, пока все элементы не станут отдельными элементами массива.
  3. Объединение — На этом шаге сформированных подмассивов объединяются в порядке сортировки .

Пример:

Сортировка массива [45, 22, 67, 14, 55, 38] с использованием сортировки слиянием.

Анализ сложности сортировки слиянием

Сортировка слиянием многократно делит массив на две части одинакового размера .

Таким образом, сложность времени сортировки слиянием зависит от количества этапов деления.

Количество ступеней деления log 2 nlog~2~nlog 2 n.

На каждом этапе слияния объединяются n элементов.

  • Шаг 1 - n×1n × 1n×1
  • Шаг 2 - n/2×2n/2 × 2n/2×2
  • Шаг 3 - н/4×4н/4×4н/4×4

Временная сложность сортировки слиянием рассчитывается с использованием времени на этап разделения. Поскольку процесс слияния имеет линейную временную сложность, для n элементов будет n*log 2 nn * log~2~nn*log 2 n этапов деления и слияния.

Следовательно, независимо от расположения, временная сложность сортировки слиянием составляет O(nlogn)O(nlogn)O(nlogn)

Анализ временной сложности сортировки слиянием

Временная сложность сортировки слиянием в наилучшем случае

Наилучший сценарий имеет место, когда элементы уже отсортированы в в порядке возрастания .
Если необходимо объединить два отсортированных массива размера n, минимальное количество сравнений будет равно n. Это происходит, когда все элементы первого массива меньше, чем элементы второго массива. Временная сложность сортировки слиянием в лучшем случае составляет O(n*logn)O(n*logn)O(n*logn).

Средняя сложность сортировки слиянием по времени

Сценарий среднего случая имеет место, когда элементы перемешаны (ни в порядке возрастания, ни в порядке убывания). Это зависит от количества сравнений. Средняя временная сложность сортировки слиянием составляет O(n*logn)O(n*logn)O(n*logn).

Наихудший случай Время сложности сортировки слиянием

Наихудший сценарий возникает, когда данный массив сортируется в порядке убывания , что приводит к максимальному количеству сравнений. В этом случае для двух отсортированных массивов размера n минимальное количество сравнений будет равно 2n. Временная сложность сортировки слиянием в наихудшем случае составляет O(n*logn)O(n*logn)O(n*logn).

Анализ сложности пространства сортировки слиянием

При сортировке слиянием все элементы копируются во вспомогательный массив размера N, где N — число элементов, присутствующих в несортированном массиве . Следовательно, пространственная сложность для сортировки слиянием составляет O(N)O(N)O(N).

Подробнее

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

Заключение

  • Сортировка слиянием — это надежный алгоритм сортировки, использующий парадигму « разделяй и властвуй ».
  • Первоначально он делит проблему на подзадачи и решает их по отдельности.
  • Затем он объединяет результаты подзадач, чтобы получить решение исходной проблемы.
  • Сортировка слиянием — это алгоритм рекурсивной сортировки .
  • Рекуррентное соотношение сортировки слиянием: T(n)=2T(n/2)+θ(n)T(n) = 2T(n/2) + θ(n)T(n)=2T(n/2)+θ(n).

    No related posts.