Стабильный Merge сорт C - PullRequest
Новая
       9

Стабильный Merge сорт C

2 голосов
/ 21 ноября 2011

Я пишу простую функцию сортировки слиянием для сортировки на основе заданной сравнения функции: 

void merge(int left, int mid, int right, int(*compar)(const void *, const void *))
{
  // sublist sizes
  int left_size = mid - left + 1;
  int right_size = right - mid;

  // counts
  int i, j, k;

  // create left and right arrays
  B *left_list = (B*) malloc(left_size*sizeof(B));
  B *right_list = (B*) malloc(right_size*sizeof(B));

  // copy sublists, could be done with memcpy()?
  for (i = 0; i < left_size; i++)
    left_list[i] = list[left + i];

  for (j = 0; j < right_size; j++)
    right_list[j] = list[mid + j + 1];

  // reset counts
  i = 0; j = 0;

  for (k = left; k <= right; k++)
  {
    if (j == right_size)
      list[k] = left_list[i++];
    else if (i == left_size)
      list[k] = right_list[j++];
    // here we call the given comparision function
    else if (compar(&left_list[i], &right_list[j]) < 0)
      list[k] = left_list[i++];
    else
      list[k] = right_list[j++];
  }
}

void sort(int left, int right, int(*compar)(const void *, const void *))
{
  if (left < right)
  {
    // find the pivot point
    int mid = (left + right) / 2;

    // recursive step
    sort(left, mid, compar);
    sort(mid + 1, right, compar);

    // merge resulting sublists
    merge(left, mid, right, compar);
  }
}

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

Кто-нибудь может подсказать причину такого поведения?

Ответы [ 2 ]

3 голосов
/ 21 ноября 2011

Я не уверен, что это сработает, но попробуйте изменить эту строку: 

compar(&left_list[i], &right_list[j]) < 0

к этому: 

compar(&left_list[i], &right_list[j]) <= 0

Это сделает так, что если они уже равны, он выполнит первое действие, которое (мы надеемся) сохранит стабильность, а не перемещает вещи.

Это всего лишь предположение.

1 голос
/ 21 ноября 2011

Я думаю, вы ошиблись 

int left_size = mid - left;

И, как указал Арасмуссен, вам нужно отдать предпочтение левому списку, чтобы сохранить стабильность 

compar(&left_list[i], &right_list[j]) <= 0

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

...