Реализация сортировки слиянием в python

Question

Я пытаюсь реализовать алгоритм сортировки слиянием в Python 3. Вот функция, которая реализует часть алгоритма слияния:

def Merge(A,p,q,r):
n1 = q - p + 1
n2 = r - q

#We first populate two lists that contain the sorted subsequences A[p,...,q] and A[q+1,...,r]
L = []
R = []

for index in range(n1):
    L.append(A[index + p])

for index in range(n2):
    R.append(A[index + q + 1])

#We now overwrite the A[p,..,q,...r] section of the list by comparing the 'top-most'
#elements in the lists l and R and putting the smaller element in the corresponding
#entry in A. If one of the list is fully exposed/no longer available, we simply put the 
#remaining list's elements in the corresponding positions in A.

i = 0
j = 0

for k in range(r - p + 1 ):

    if i > n1-1:
        A[k] = R[j]
        j = j + 1

    elif j > n2-1:
        A[k] = L[i]
        i = i + 1

    elif L[i] < R[j]:
        A[k] = L[i]
        i = i + 1

    else:
        A[k] = R[j]
        j = j + 1 

return A   

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

import math

def Merge_Sort(A,p,r):

if p == r:

    return A

if p < r:

    q = math.floor((p+r)/2)
    Merge_Sort(A,p,q)
    Merge_Sort(A,q+1,r)
    Merged_List = Merge(A,p,q,r)

return Merged_List

Но я получаю ошибочные ответы, когда запускаю его. Вот пример:

#We now analyze the merge sort algorithm.
A = [1,7,9,3]
B = Merge_Sort(A,0,3)
print(B)

Результат:

[3, 9, 3, 9]

Я, вероятно, совершаю очевидную / глупую ошибку при реализации бита «разделяй и властвуй». Предложения?

Answer 1

Ошибка в присвоении A[k]. Их следует заменить на присвоения A[p+k].

Обратите внимание, что L и R могут быть определены с использованием следующего синтаксиса (без явного l oop):

L = A[p:q+1]
R = A[q+1:r+1]

Чтобы соответствовать тому, как работают собственные функции в Python (например, list.extend), ваши две функции должны не возвращать список. Они изменяют список, который вы передаете в качестве аргумента, поэтому, чтобы избежать путаницы, лучше не возвращать его: это может заставить пользователей вашего кода подумать, что функция не имеет побочных эффектов.

Answer 2

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

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)

* 1003 проблема в функции слияния. Где вы должны назначить элементы массива L и массива R. Ваш начальный индекс - p, поэтому вы должны назначить L [i] и R [i] для A [p + k] вместо A [k ]. Если у вас все еще есть сомнения относительно сортировки слиянием, обратитесь к Сортировка слиянием . надеюсь, что это решит все ваши вопросы. Спасибо