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

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

void mergesort(int A[],int start,int end)
{
    int B[(end-start)/2],C[(end-start)/2],i,j,k,flag=0;
    if(start==end)
      return;
    else
    {
      mergesort(A,start,(start+end)/2);
      mergesort(A,(start+end)/2+1,end);
    }
    for(i=start;i<(start+end)/2;i++)
      B[i]=A[i];
    for(i=(start+end)/2+1;i<end;i++)
      C[i]=A[i];
    for(i=start,j=start,k=(start+end)/2+1;i<end;i++)
    {
        if(j==(start+end)/2)
        {
            while(k!=end)
              A[i]=C[k++];
            flag=1;
        }
        if(k==end)
        {
            while(j!=(start+end)/2)
              A[i]=B[j++];
            flag=1;
        }
        if(flag)
          break;
        if(A[j]&gt;C[k])
          A[i]=C[k++];
        else
          A[i]=B[j++];
    }
    return;
}

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


person user3600483    schedule 18.07.2014    source источник
comment
У меня есть рекурсивная реализация MergeSort, она на С#, но если вы рассматриваете IList<T> как массив, вы сможете легко реализовать ее на C. Я не слишком внимательно смотрел на ваш код, потому что он потребует отладки.   -  person Lasse V. Karlsen    schedule 18.07.2014
comment
во-первых, используя переменную mid = (start+end)/2, вы предотвратите появление у читателей рака мозга :)   -  person Vikram Bhat    schedule 18.07.2014
comment
Тогда массивы B и C могут быть не одинаковой длины (для нечетного числа элементов). И копия с A на B и C не корректна. Индекс для B и C необходимо сдвинуть, чтобы он начинался с 0. То же самое относится ко всем другим расчетам индекса.   -  person Nico Schertler    schedule 18.07.2014
comment
Не могли бы вы предоставить более подробную информацию о том, что именно не работает?   -  person Codor    schedule 18.07.2014
comment
вы должны создать разные функции для разделения и слияния. Разделение будет рекурсивным, и поскольку в любой момент два подмассива не могут быть одинакового размера, используйте индексирование для отслеживания двух подмассивов, скажем, индекс, из которого вы делите один массив на два, назовите его mid и два подмассива будут [от начала до середины] и [от середины+1 до конца] и делают то же самое до start < end . так что дело в работе над индексами и отдельными функциями разделения и сортировки! держать вещи простыми .! ссылка [cormen the best] (personal.kent.edu/ ~rmuhamma/Алгоритмы/Мои Алгоритмы/Сортировка/)   -  person Hima    schedule 18.07.2014


Ответы (2)


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

mergesort(A,start,(start+end)/2); // should be (start+end)/2+1 if end is excluded
mergesort(A,(start+end)/2+1,end);
person dohashi    schedule 18.07.2014
comment
не совсем, даже если он исключен в первом, он будет включен во вторую рекурсию, так что в любом случае ответ будет таким же - person Vikram Bhat; 18.07.2014
comment
Если код исключает конечные точки (как кажется), элемент в A[(start+end)/2] не обрабатывается ни первым, ни вторым вызовом. - person dohashi; 18.07.2014

Убийственная проблема заключается в том, что петля

for(i=(start+end)/2+1;i<end;i++)
  C[i]=A[i];

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

person user58697    schedule 18.07.2014