Реализация сортировки слиянием вообще в C - PullRequest
Новая
       6

Реализация сортировки слиянием вообще в C

0 голосов
/ 05 июня 2019

Я пытаюсь создать общую реализацию сортировки слиянием.Я на 99% уверен, что проблема связана с тем, что я неправильно использую memcpy.

Вот код, который у меня есть для объединения 2 массивов: 

static inline void * merge(void *left, void *right,
          size_t leftsz, size_t rightsz, size_t width, DArray_compare cmp)
{
  size_t i = 0, k = 0, j = 0;
  size_t sz = leftsz + rightsz;
  void *res = NULL;

  res = calloc(sz, width);
  check_mem(res);

  while (j < sz) {
    if (i == leftsz) {
      memcpy(res + j*width, right + k*width, width);
      ++i;
    } else if (k == rightsz) {
      memcpy(res + j*width, left + i*width, width);
      ++k;
    } else if (cmp(left + i*width, right + k*width) < 0) {
      debug("Here");
      memcpy(res + j*width, left + i*width, width);
      ++i;
    } else {
      memcpy(res + j*width, right + k*width, width);
      ++k;
    }

    debug("------PRINTING RES------\n");
    for (int t = 0; t < j; t++) {
      debug("%s\n", * (char **) res + t);
    }
    debug("----FINISHED PRINTING RES----\n");

    ++j;
  }

  return res;

error:
  return NULL;
}

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

Всякий раз, когда я запускаю это для массива { "asdfasfd", "werwar", "13234", "asdfasfd", "oioj" }, он говорит, что массив был отсортирован неправильно.

Вот основной код сортировки слиянием: 

int merge_sort(void *arr, size_t size,
      size_t width, DArray_compare cmp)
{
  if (size <= 1)
    return 0;

  size_t lsize = size / 2, rsize = size - (size / 2);
  void *left = NULL, *right = NULL, *res = NULL;

  left = calloc(lsize, width);
  check_mem(left);

  right = calloc(rsize, width);
  check_mem(right);

  memcpy(left, arr, lsize*width);
  memcpy(right, arr + lsize*width, rsize*width);

  debug("Looping over right array.");
  for (int i = lsize; i < size; i++) {
    debug("%s", * ((char **) right + (i-lsize)));
  }

  merge_sort(left, lsize, width, cmp);
  merge_sort(right, rsize, width, cmp);


  res = merge(left, right, lsize, rsize, width, cmp);
  check_mem(res);

  free(left);
  free(right);

  memcpy(arr, res, size*width);
  free(res);

  return 0;

error:
  if (left) free(left);
  if (right) free(right);
  if (res) free(res);
  return -1;
}

Опять же, я уверен, что моя реализация не работает из-за memcpy.Тем не менее, я не совсем уверен, как именно я использую это неправильно.

Я запустил функцию merge_sort над массивом { "asdfasfd", "werwar", "13234", "asdfasfd", "oioj" } примерно так: 

int rc = merge_sort(words->contents, words->end,
        sizeof(void *), (DArray_compare) testcmp);
...

words->contentsэто void ** массив, а words->end это размер массива.words сама структура представляет собой динамический массив.Я знаю, что массив был построен правильно, поэтому я не думаю, что это корень проблемы.

Не стесняйтесь спрашивать меня, если нужно, дополнительную информацию.

Спасибо.

Редактировать:

Вот пример: 

int main(int argc, char *argv[])
{
  char *words[] = { "asdfasfd",
      "werwar", "13234", "asdfasfd", "oioj"};
  merge_sort((void **)&words, 5,
        sizeof(void *), testcmp);
  for (int i = 0; i < 4; i++) {
      if (strcmp(words[i], words[i+1]) > 0) {
          printf("NOT SORTED\n");
          return 1;
      }
  }
  return 0;
}

1 Ответ

0 голосов
/ 05 июня 2019

Хорошо, похоже, я был не прав, почему сортировка слиянием не удалась.

Как сказал Йен Эбботт, if (i == leftsz) должно быть if (i >= leftsz), и то же самое должно было пойти на (k == rightsz). Это предотвращает копирование данных после конца массива. Большое спасибо!

Edit:

Кроме того, перед циклом j я добавил следующее: 

for (int t = 0; t < sz; t++) {
    char *ptr = res + t*width;
    ptr = calloc(1, width);
    check_mem(ptr);
}

Без этого раздела кода вышеописанное не работает.

...