Что не так с моим кодом сортировки слиянием?

Question

Я учусь кодировать, и, хотя я попробую написать алгоритм сортировки слиянием (о чем мы слышали в нашем аналитическом курсе, но НЕ домашнюю работу). Я работал с псевдокодом, который показал нам тренер, но я не могу определить проблему. Есть ли шанс, что кто-нибудь может указать мне правильное направление?

edit: алгоритм возвращает только первое значение в списке.

static List<int> mergeSort(List<int> mj)
{
    List<int>m = mj;
    if(m.Count <= 1)
        return m;
    List<int> merge = new List<int>();

    List<int> left = new List<int>();
    List<int> right = new List<int>();
    int middle = m.Count/2;

    for (int i = 0; i < middle; i++)
        left.Add(m[i]);
    for (int j = middle; j >= m.Count; j++)
        right.Add(m[j]);

    left = mergeSort(left);
    right = mergeSort(right);

    merge.AddRange(left);
    merge.AddRange(right);

    for (int k = 0; k < merge.Count; k++)
    {
        Console.Write(merge[k] + ",");
    }
    return merge;

}

Answer 1

Проблема с вашим кодом (за исключением ошибки, упомянутой Майком Коуэном) заключается в том, что вы не выполняете никакой реальной сортировки. Сначала вы рекурсивно разбиваете свои списки пополам (что правильно), но затем вы просто объединяете их вместе в их первоначальном порядке, что не дает результата:

merge.AddRange(left);
merge.AddRange(right);

Вместо этого вам нужно перебрать два ваших подсписка (которые по индукции должны были быть соответственно отсортированы в рекурсивных вызовах) и добавить элементы в объединенный список в порядке .

Мы начнем со сравнения элементов 0 ^th : left[0] с right[0]. В зависимости от того, какое из двух значений меньше, оно добавляется в список merge, а счетчик его подсписка увеличивается. Предположим, что left[0] < right[0]: мы добавляем left[0] к merge, и на следующей итерации нам потребуется рассмотреть left[1] против right[0]. Если left[1] снова меньше, мы добавляем его к merge и на следующей итерации рассмотрим left[2] против right[0]. Если right[0] теперь меньше из двух, мы добавляем it к merge и на следующей итерации сравниваем left[2] с right[1]. И так далее.

Это продолжается до тех пор, пока один из подсписков не будет исчерпан. Когда это происходит, мы просто добавляем все элементы из оставшегося подсписка в merge.

int leftIndex = 0;        
int rightIndex = 0;

while (leftIndex < left.Count && rightIndex < right.Count)
    if (left[leftIndex] < right[rightIndex])
        merge.Add(left[leftIndex++]);
    else
        merge.Add(right[rightIndex++]);

while (leftIndex < left.Count)
    merge.Add(left[leftIndex++]);
while (rightIndex < right.Count)
    merge.Add(right[rightIndex++]);

Кроме того, вы не должны писать в консоль в пределах вашего рекурсивного метода. Переместите Console.Write звонки на ваш Main метод:

static void Main(string[] args)
{
    List<int> original = new List<int>(new int[] { 4, 75, 12, 65, 2, 71, 56, 33, 78,1, 4, 56, 85, 12, 5,77, 32, 5 });
    List<int> sorted = mergeSort(original);

    for (int k = 0; k < sorted.Count; k++)
        Console.Write(sorted[k] + ",");
}

Answer 2

Эта строка:

for (int j = middle; j >= m.Count; j++)
    right.Add(m[j]);

следует читать:

for (int j = middle; j < m.Count; j++)
    right.Add(m[j]);

Answer 3

Во-первых, строка

for (int j = middle; j >= m.Count; j++)

должна быть

for (int j = middle; j < m.Count; j++)

Кроме того, вы фактически никогда не объединяете левое и правое, вы просто размещаете их поверх друг друга.Строка

merge.AddRange(left);
merge.AddRange(right);

должна выглядеть примерно так:

mergeLeftRight(left, right)

Где mergeLeftRight - это вторая определяемая вами функция, которая выполняет фактическую сортировку.Прочитайте статью в Википедии о сортировке слиянием: http://en.wikipedia.org/wiki/Merge_sort

Answer 4

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

1. if (mj.length == 1) return mj;
2. Разделение на левый и правый списки и повторение
3. , когда левый и правый списки возвращаются, объедините их <- вы не делаете этого </strong>
4. returnобъединены левый и правый списки