Объяснение слияния Сортировка для чайников

Ответ 1

Я считаю, что ключом к пониманию типа слияния является понимание следующего принципа: я назову его принципом слияния:

Учитывая, что два отдельных списка A и B упорядочены от наименьшего к наибольшему, постройте список C, повторно сравнивая наименьшее значение A с наименьшим значением B, удаляя меньшее значение и добавляя его на C. Когда один список исчерпаны, добавьте оставшиеся предметы в другом списке на C в порядке. Список C также является отсортированным списком.

Если вы немного разобрались с этим вручную, вы увидите, что это правильно. Например:

A = 1, 3
B = 2, 4
C = 
min(min(A), min(B)) = 1

A = 3
B = 2, 4
C = 1
min(min(A), min(B)) = 2

A = 3
B = 4
C = 1, 2
min(min(A), min(B)) = 3

A = 
B = 4
C = 1, 2, 3

Теперь A исчерпан, поэтому продолжите C с остальными значениями из B:

C = 1, 2, 3, 4

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

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

Теперь, учитывая этот принцип, очень легко понять метод сортировки, сортирующий список, деля его на более мелкие списки, сортировку этих списков и объединение этих отсортированных списков вместе. Функция merge_sort - это просто функция, которая разделяет список пополам, сортирует эти два списка и затем объединяет эти два списка вместе, как описано выше.

Единственный улов в том, что, поскольку он рекурсивный, когда он сортирует два подписок, он делает это, передавая их себе! Если вам трудно понять рекурсию здесь, я бы предложил сначала изучить более простые проблемы. Но если вы уже освоите основы рекурсии, то все, что вам нужно понять, это то, что список из одного элемента уже отсортирован. Объединение двух списков с одним элементом создает отсортированный список из двух элементов; объединение двух списков двух элементов генерирует отсортированный список из четырех элементов; и так далее.

Ответ 2

Когда я наткнулся на diffuculty, чтобы понять, как работает алгоритм, я добавляю вывод отладки, чтобы проверить, что действительно происходит внутри алгоритма.

Здесь код с отладочным выходом. Попробуйте выполнить все шаги с рекурсивными вызовами mergesort и что merge делает с выходом:

def merge(left, right):
    result = []
    i ,j = 0, 0
    while i < len(left) and j < len(right):
        print('left[i]: {} right[j]: {}'.format(left[i],right[j]))
        if left[i] <= right[j]:
            print('Appending {} to the result'.format(left[i]))           
            result.append(left[i])
            print('result now is {}'.format(result))
            i += 1
            print('i now is {}'.format(i))
        else:
            print('Appending {} to the result'.format(right[j]))
            result.append(right[j])
            print('result now is {}'.format(result))
            j += 1
            print('j now is {}'.format(j))
    print('One of the list is exhausted. Adding the rest of one of the lists.')
    result += left[i:]
    result += right[j:]
    print('result now is {}'.format(result))
    return result

def mergesort(L):
    print('---')
    print('mergesort on {}'.format(L))
    if len(L) < 2:
        print('length is 1: returning the list withouth changing')
        return L
    middle = len(L) / 2
    print('calling mergesort on {}'.format(L[:middle]))
    left = mergesort(L[:middle])
    print('calling mergesort on {}'.format(L[middle:]))
    right = mergesort(L[middle:])
    print('Merging left: {} and right: {}'.format(left,right))
    out = merge(left, right)
    print('exiting mergesort on {}'.format(L))
    print('#---')
    return out


mergesort([6,5,4,3,2,1])

Вывод:

---
mergesort on [6, 5, 4, 3, 2, 1]
calling mergesort on [6, 5, 4]
---
mergesort on [6, 5, 4]
calling mergesort on [6]
---
mergesort on [6]
length is 1: returning the list withouth changing
calling mergesort on [5, 4]
---
mergesort on [5, 4]
calling mergesort on [5]
---
mergesort on [5]
length is 1: returning the list withouth changing
calling mergesort on [4]
---
mergesort on [4]
length is 1: returning the list withouth changing
Merging left: [5] and right: [4]
left[i]: 5 right[j]: 4
Appending 4 to the result
result now is [4]
j now is 1
One of the list is exhausted. Adding the rest of one of the lists.
result now is [4, 5]
exiting mergesort on [5, 4]
#---
Merging left: [6] and right: [4, 5]
left[i]: 6 right[j]: 4
Appending 4 to the result
result now is [4]
j now is 1
left[i]: 6 right[j]: 5
Appending 5 to the result
result now is [4, 5]
j now is 2
One of the list is exhausted. Adding the rest of one of the lists.
result now is [4, 5, 6]
exiting mergesort on [6, 5, 4]
#---
calling mergesort on [3, 2, 1]
---
mergesort on [3, 2, 1]
calling mergesort on [3]
---
mergesort on [3]
length is 1: returning the list withouth changing
calling mergesort on [2, 1]
---
mergesort on [2, 1]
calling mergesort on [2]
---
mergesort on [2]
length is 1: returning the list withouth changing
calling mergesort on [1]
---
mergesort on [1]
length is 1: returning the list withouth changing
Merging left: [2] and right: [1]
left[i]: 2 right[j]: 1
Appending 1 to the result
result now is [1]
j now is 1
One of the list is exhausted. Adding the rest of one of the lists.
result now is [1, 2]
exiting mergesort on [2, 1]
#---
Merging left: [3] and right: [1, 2]
left[i]: 3 right[j]: 1
Appending 1 to the result
result now is [1]
j now is 1
left[i]: 3 right[j]: 2
Appending 2 to the result
result now is [1, 2]
j now is 2
One of the list is exhausted. Adding the rest of one of the lists.
result now is [1, 2, 3]
exiting mergesort on [3, 2, 1]
#---
Merging left: [4, 5, 6] and right: [1, 2, 3]
left[i]: 4 right[j]: 1
Appending 1 to the result
result now is [1]
j now is 1
left[i]: 4 right[j]: 2
Appending 2 to the result
result now is [1, 2]
j now is 2
left[i]: 4 right[j]: 3
Appending 3 to the result
result now is [1, 2, 3]
j now is 3
One of the list is exhausted. Adding the rest of one of the lists.
result now is [1, 2, 3, 4, 5, 6]
exiting mergesort on [6, 5, 4, 3, 2, 1]
#---

Ответ 3

Несколько способов помочь вам понять это:

Пройдите код в отладчике и посмотрите, что произойдет. Или, Пройдите через него на бумаге (с очень маленьким примером) и посмотрите, что происходит.

(лично я считаю, что делать такие вещи на бумаге более поучительными)

Концептуально он работает следующим образом: Список входных данных продолжает раскалываться на более мелкие и мелкие куски, уменьшая вдвое (например, list[:middle] - первая половина). Каждая половина уменьшается вдвое и снова до тех пор, пока она не будет иметь длину менее 2. I.e. пока это не будет вообще ни одним элементом. Эти отдельные части затем объединяются с помощью процедуры слияния, добавляя или перемежая 2 вспомогательных списка в список result, и, следовательно, вы получаете отсортированный список. Поскольку 2 вспомогательных списка должны быть отсортированы, добавление/чередование - это быстрая (O (n)) операция.

Ключ к этому (по моему мнению) не является процедурой слияния, что довольно очевидно, если вы понимаете, что входные данные для него всегда будут отсортированы. "Трюк" (я использую цитаты, потому что это не трюк, это компьютерная наука:-)) заключается в том, что для того, чтобы гарантировать, что входы для объединения сортируются, вам нужно продолжать рекурсию, пока не попадете в список, который нужно отсортировать, и поэтому вы продолжаете рекурсивно вызывать mergesort, пока список не будет содержать менее двух элементов.

Рекурсия и сортировка слияния расширения могут быть неочевидными, когда вы впервые сталкиваетесь с ними. Вы можете обратиться к хорошей книге алгоритмов (например, DPV доступен онлайн, легально и бесплатно), но вы можете пройти долгий путь, шагнув через код, который у вас есть. Если вы действительно захотите войти в него, скоро будет запущен курс альфа-курса Stanford/Coursera , и он подробно рассмотрит сортировку Merge.

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

Ответ 4

Сортировка слияний всегда была одним из моих любимых алгоритмов.

Вы начинаете с коротких отсортированных последовательностей и продолжаете сгруппировать их, чтобы упорядочить последовательности. Так просто.

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

Ответ 5

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

Ответ 6

У вас может быть хорошая визуализация того, как работает сортировка слияния:

http://www.ee.ryerson.ca/~courses/coe428/sorting/mergesort.html

Надеюсь, это поможет.

Ответ 7

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

Я не буду отвечать на этот вопрос, используя Python, просто потому, что я не могу его написать; однако, принятие части алгоритма "сортировки слияния", по-видимому, в самом центре вопроса. Ресурсом, который мне помог, является KITE довольно устаревшая веб-страница по алгоритму (написанная профессором), просто потому, что автор контента исключает контекстно- значимые идентификаторы.

Мой ответ получен из этого ресурса.

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

Вот, это "код" (посмотрите на конец скрипта Java):

public class MergeSort {

/**
 * @param a     the array to divide
 * @param low   the low INDEX of the array
 * @param high  the high INDEX of the array
 */
public void divide (int[] a, int low, int high, String hilo) {


    /* The if statement, here, determines whether the array has at least two elements (more than one element). The
     * "low" and "high" variables are derived from the bounds of the array "a". So, at the first call, this if 
     * statement will evaluate to true; however, as we continue to divide the array and derive our bounds from the 
     * continually divided array, our bounds will become smaller until we can no longer divide our array (the array 
     * has one element). At this point, the "low" (beginning) and "high" (end) will be the same. And further calls 
     * to the method will immediately return. 
     * 
     * Upon return of control, the call stack is traversed, upward, and the subsequent calls to merge are made as each 
     * merge-eligible call to divide() resolves
     */
    if (low < high) {
        String source = hilo;
        // We now know that we can further divide our array into two equal parts, so we continue to prepare for the division 
        // of the array. REMEMBER, as we progress in the divide function, we are dealing with indexes (positions)

        /* Though the next statement is simple arithmetic, understanding the logic of the statement is integral. Remember, 
         * at this juncture, we know that the array has more than one element; therefore, we want to find the middle of the 
         * array so that we can continue to "divide and conquer" the remaining elements. When two elements are left, the
         * result of the evaluation will be "1". And the element in the first position [0] will be taken as one array and the
         * element at the remaining position [1] will be taken as another, separate array.
         */
        int middle = (low + high) / 2;

        divide(a, low, middle, "low");
        divide(a, middle + 1, high, "high");


        /* Remember, this is only called by those recursive iterations where the if statement evaluated to true. 
         * The call to merge() is only resolved after program control has been handed back to the calling method. 
         */
        merge(a, low, middle, high, source);
    }
}


public void merge (int a[], int low, int middle, int high, String source) {
// Merge, here, is not driven by tiny, "instantiated" sub-arrays. Rather, merge is driven by the indexes of the 
// values in the starting array, itself. Remember, we are organizing the array, itself, and are (obviously
// using the values contained within it. These indexes, as you will see, are all we need to complete the sort.  

    /* Using the respective indexes, we figure out how many elements are contained in each half. In this 
     * implementation, we will always have a half as the only way that merge can be called is if two
     * or more elements of the array are in question. We also create to "temporary" arrays for the 
     * storage of the larger array elements so we can "play" with them and not propogate our 
     * changes until we are done. 
     */
    int first_half_element_no       = middle - low + 1;
    int second_half_element_no      = high - middle;
    int[] first_half                = new int[first_half_element_no];
    int[] second_half               = new int[second_half_element_no];

    // Here, we extract the elements. 
    for (int i = 0; i < first_half_element_no; i++) {  
        first_half[i] = a[low + i]; 
    }

    for (int i = 0; i < second_half_element_no; i++) {  
        second_half[i] = a[middle + i + 1]; // extract the elements from a
    }

    int current_first_half_index = 0;
    int current_second_half_index = 0;
    int k = low;


    while (current_first_half_index < first_half_element_no || current_second_half_index < second_half_element_no) {

        if (current_first_half_index >= first_half_element_no) {
            a[k++] = second_half[current_second_half_index++];
            continue;
        }

        if (current_second_half_index >= second_half_element_no) {
            a[k++] = first_half[current_first_half_index++];
            continue;
        }

        if (first_half[current_first_half_index] < second_half[current_second_half_index]) {
            a[k++] = first_half[current_first_half_index++];
        } else {
            a[k++] = second_half[current_second_half_index++];
        }
    }
}

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

Ответ 8

Изображение стоит тысячи слов, а анимация стоит 10 000.

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

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

Еще одна интересная анимация различных типов алгоритмов сортировки.