Рубрики

Программа Python для сортировки слиянием

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

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

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

def merge(arr, l, m, r):

    n1 = m - l + 1

    n2 = r- m

  

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

    L = [0] * (n1)

    R = [0] * (n2)

  

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

    for i in range(0 , n1):

        L[i] = arr[l + i]

  

    for j in range(0 , n2):

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

  

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

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

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

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

  

    while i < n1 and j < n2 :

        if L[i] <= R[j]:

            arr[k] = L[i]

            i += 1

        else:

            arr[k] = R[j]

            j += 1

        k += 1

  

    # Скопируйте оставшиеся элементы L [], если есть

    # любые

    while i < n1:

        arr[k] = L[i]

        i += 1

        k += 1

  

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

    # любые

    while j < n2:

        arr[k] = R[j]

        j += 1

        k += 1

  
# l для левого индекса и r это правый индекс
# подмассив arr для сортировки

def mergeSort(arr,l,r):

    if l < r:

  

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

        # большие л и ч

        m = (l+(r-1))/2

  

        # Сортировать первую и вторую половинки

        mergeSort(arr, l, m)

        mergeSort(arr, m+1, r)

        merge(arr, l, m, r)

  

  
# Код драйвера для проверки выше

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

n = len(arr)

print ("Given array is")

for i in range(n):

    print ("%d" %arr[i]),

  

mergeSort(arr,0,n-1)

print ("\n\nSorted array is")

for i in range(n):

    print ("%d" %arr[i]),

  
# Этот код предоставлен Мохитом Кумрой

Выход:

Given array is
12 11 13 5 6 7 

Sorted array is
5 6 7 11 12 13

Пожалуйста, обратитесь к полной статье о сортировке слиянием для более подробной информации!

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

Программа Python для сортировки слиянием

0.00 (0%) 0 votes