Почему функция Merge () Merge Sort имеет условный второй цикл? - PullRequest
Новая
       5

Почему функция Merge () Merge Sort имеет условный второй цикл?

1 голос
/ 24 апреля 2010 
merge1(int low, int high, int S[], U[]) 
{ 
    int k = (high - low + 1)/2
    for q (from low to high) U[q] = S[q]
    int j = low 
    int p = low 
    int i = low + k 

    while (j <= low + k - 1) and (i <= high) do 
    { 
        if ( U[j] <= U[i] ) 
        {
            S[p] := U[j] 
            j := j+1
        } 
        else 
        { 
            S[p] := U[i] 
            i := i+1 
        } 
        p := p+1 
    } 

    if (j <= low + k - 1) 
    { 
        for q from p to high do 
        { 
            S[q] := U[j] 
            j := j+1 
        } 
    }
}


merge_sort1(int low, int high, int S[], U[]) 
{ 
    if low < high 
    { 
        int k := (high - low + 1)/2 
        merge_sort1(low, low+k-1, S, U) 
        merge_sort1(low+k, high, S, U) 
        merge1(low, high, S, U) 
    } 
}

Итак, в основном, это в моих конспектах. Я нахожу это довольно запутанным в целом, но я понимаю большую часть этого. Что я не понимаю, так это необходимость части "if (j <= low + k - 1)". Похоже, он проверяет, есть ли в левой части какие-либо элементы. Это возможно даже при слиянии? </p>

1 Ответ

2 голосов
/ 24 апреля 2010

При объединении двух отсортированных списков (назовем их left и right), вы продолжаете брать один элемент и добавлять его в список result, пока у вас не закончатся элементы либо в left, либо right список. Это делается с помощью первого цикла while. Теперь вам нужно добавить элементы, оставшиеся в левом или правом списке, в список результатов. Есть два варианта:

  • В левом списке нет элементов, а в правом списке все еще есть некоторые. То, как код написан здесь, нам не нужно ничего делать, так как конец массива S уже содержит последние элементы в списке right.

  • В правом списке нет элементов, а в левом списке все еще есть некоторые. Затем мы копируем оставшиеся элементы в конец S. Это то, что делает if в конце merge1.

Относительно вашего вопроса, если этот код "плохой": код правильный, но я хотел бы внести некоторые изменения, чтобы сделать его более читабельным:

  • Описательные имена переменных.
  • Передача средней точки, разделяющей списки left и right, на merge1 вместо ее пересчета.
...