Почему не работает мой mergesort?

Question

[Нодар]

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

Уже несколько дней бьюсь надо merge sort, делаю по псевдокоду описанному в Introduction to Algorithms.

void
merge(int *array, int start, int mid, int end)
{ 

  int leftLen = mid - start,
      rightLen = end - mid,
      left[leftLen], right[rightLen],
      i, j, k;

  for (i = 0; i < leftLen; i++) {
    left[i] = array[start+i];
  }

  for (j = 0; j < rightLen; j++) {
    right[j] = array[mid+j];
  }

  i = 0;
  j = 0;
  
  for (k = start; k < end; k++) {
    if ((i < leftLen && left[i] < right[j]) || j >= rightLen) {
      array[k] = left[i];
      i++;
    } else {
      array[k] = right[j];
      j++;
    }
  }
}


void mergeSort(int *array, int start, int end)
{
  int mid = (start + end) / 2;
  if (start < end) {
    mergeSort(array, start, mid);
    mergeSort(array, mid+1, end);
    merge(array, start, mid, end);
  }
}


int
main(int argc, const char *argv[])
{
  int array[] = {3,2,6,4,1,8,7,9,5},
      arrayLen = sizeof(array)/sizeof(int);

  mergeSort(array, 0, arrayLen);
}

Буду признателен за помощь.

Comments

[Mrrl]

Сначала опишите, что значит "не работает". Он не компилируется? Выдаёт ошибку при запуске? Зависает? Или выдаёт неправильный результат?
Пока могу сказать, что это не может быть "чистым С". Вероятно, это какая-нибудь современная версия С++.

[Нодар]

Писал это на основе чтива от товарищей Кернигана и Ритчи. Платформа OS X, компилятор gcc

[Нодар]

Mrrl: выдает неверный результат

[Mrrl]

Керниган и Ритчи знали про const? Интересный факт.

Answer 1

[Mrrl]

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

if ((i < leftLen && left[i] < right[j]) || j >= rightLen) {

В случае, когда j==rightLen, у вас будет проверяться элемент right[j]. Условия здесь надо поменять местами:

if ( j >= rightLen || (i < leftLen && left[i] < right[j])) {

Вторая - что элемент array[mid] не будет участвовать ни в первом, ни во втором рекурсивных вызовах mergeSort. Второй вызов надо было сделать
mergeSort(array, mid, end);
А чтобы не было бесконечной рекурсии, изменить условие в mergeSort на
if (start < end-1) {
(или на if(start < mid) ).

Ну, и в классическом С невозможна конструкция

int leftLen = mid - start,
      left[leftLen];

Там массивы могут быть только фиксированной длины, а для динамического захвата приходится использовать malloc. Но если компилируется, значит, ваша версия компилятора такое позволяет.

UPD. В С99 действительно возможны массивы переменной длины, и пишут, что gcc их поддерживает. Ну и ладно. Visual Studio такое не позволяет.

Comments

[Нодар]

Спасибо! Теперь все работает, как и положено.

Answer 2

[Mercury13]

int left[leftLen]

Будь осторожен, на «боевых» задачах чревато переполнением стека. Стек вызовов невелик, всего ничего единицы мегабайт.

Comments

[Нодар]

Вы про динамическое определение длины массива? После Python, Ruby тяжело с таким свыкнуться...

[Mercury13]

Динамическое задание массива работает крайне просто. Указатель стека смещается вниз (к верхушке, на x86 стек растёт вниз), и на появившемся месте располагается массив.

[Нодар]

Спасибо за совет.

[Mercury13]

P.S. Ну, а если захочешь делать в куче — обычный calloc. Только удалить не забудь.