Понимание алгоритма сортировки слиянием - PullRequest
Новая
       17

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

0 голосов
/ 05 марта 2019

Я прохожу алгоритм сортировки слиянием и пытаюсь рекурсивно понять его подход, используя этот фрагмент алгоритма: 

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)

Я попытался запустить его для массива размером 3. 

[0,1,2]
mergesort(A,0,2)----[0,1,2]
mergesort(A,0,1)----[0,1]
mergesort(A,0,0)----[0]
mergesort(A,1,2)----[1,2]
mergesort(A,2,2)----[2]
merge(A,0,1,2)

Хотя я в состоянии понять его основную технику «разделяй и властвуй», но я не могу правильно бегать. Я знаю, что что-то упускаю. Кто-нибудь может мне помочь или указать на недостающую часть.

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

1 Ответ

2 голосов
/ 06 марта 2019

Если необходимо исправить: 

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)

пример пробного прогона с отступом для уровня рекурсии 

[0,1,2]
mergesort(A,0,2)--------[0,1,2]
  mergesort(A,0,1)------[0,1]
    mergesort(A,0,0)----[0]
    mergesort(A,1,1)----[1]
    merge(A,0,0,1)------[0]+[1]
  mergesort(A,2,2)------[2]
  merge(A,0,1,2)--------[0,1]+[2]

Изменение переменных на b (начало), e (конец = последний + 1), m (середина) 

MergeSort(A, b, e)
If (e - b) < 2
    return;
m = (b+e)/2;
mergeSort(A, b, m) 
mergeSort(A, m, e)
merge(A, b, m, e)

пример пробного прогона 

[0,1,2]
mergesort(A,0,3)--------[0,1,2]
  mergesort(A,0,1)------[0]
  mergesort(A,1,3)------[1,2]
    mergesort(A,1,2)----[1]
    mergesort(A,2,3)----[2]
    merge(A,1,2,3)------[1]+[2]
  merge(A,0,1,3)--------[0]+[1,2]

другой пример пробного прогона 

[0,1,2,3]
mergesort(A,0,4)--------[0,1,2,3]
  mergesort(A,0,2)------[0,1]
    mergesort(A,0,1)----[0]
    mergesort(A,1,2)----[1]
    merge(A,0,1,2)------[0]+[1]
  mergesort(A,2,4)------[2,3]
    mergesort(A,2,3)----[2]
    mergesort(A,3,4)----[3]
    merge(A,2,3,4)------[2]+[3]
  merge(A,0,2,4)--------[0,1]+[2,3]
...