Блог

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

Например: Ввод: 2 2 3 7 1 2 1 . Вывод: 2 2 3 7 0 1 1 .

Теперь я пытаюсь найти ошибку в своем коде. Вот оно:

 #include <stddef.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "MergeSort.h"

int StrCmp(char *st1, char *st2) {
    char *str1 = st1, *str2 = st2;
    while (*str1 == *str2 amp;amp; *str1 != 0)
        str1  , str2  ;
    return *str1 - *str2;
}

int CompareInt(void *a, void *b) {
    return *(int *)a - *(int *)b;
}

int CompareChar(void *a, void *b) {
    return *(char *)a - *(char *)b;
}

int CompareStr(const void *a, const void *b) {
    return strcmp(*(char **)a, *(char **)b);
}

int merge(void *base, size_t num, size_t el_size, int (*compar)(const void*, const void*)) {
    size_t size = (size_t)num / 2;
    char *char_base = (char *)base;
    char *first = malloc(size * el_size);
    char *second = malloc((num - size) * el_size);

    for (int i = 0; i < size; i  )
        for (int j = 0; j < el_size; j  )
            first[i * el_size   j] = char_base[i * el_size   j];

    for (int i = 0; i < num - size; i  )
        for (int j = 0; j < el_size; j  )
            second[i * el_size   j] = char_base[size * el_size   i * el_size   j];

    size_t i = 0, j = 0, c = 0;
    while (i < size amp;amp; j < num - size) {
        if (compar(amp;first[i * el_size], amp;second[j * el_size]) <= 0) {
            for (int k = 0; k < el_size; k  ) 
                char_base[el_size * c   k] = first[i * el_size   k];
            i  ;
        } else { 
            for (int k = 0; k < el_size; k  ) 
                char_base[el_size * c   k] = second[j * el_size   k];
            j  ;
        }
        c  ;
    }

    if (i == size) { 
        while (j < num - size) {
            for (int k = 0; k < el_size; k  ) 
                char_base[el_size * c   k] = second[j * el_size   k];
            j  ;
            c  ;
        }
    } else { 
        while (i < size) {
            for (int k = 0; k < el_size; k  ) 
                char_base[el_size * c   k] = first[i * el_size   k];
            i  ;
            c  ;
        }
    }
    free(first);
    free(second);
}

int merge_sort(void *base, size_t num, size_t el_size, int (*compar)(const void*, const void*)) {
    if (num > 1) {
        size_t s = num / 2;
        char *char_base = base;
        merge_sort(char_base, s, el_size, compar);
        merge_sort(char_base   (num - s) * el_size, num - s, el_size, compar);
        merge(char_base, num, el_size, compar);
    }
}

int main() {
    int nums[] = { 2, 2, 3, 7, 1, 2, 1 };
    cmp_t cmp = CompareInt;
    merge_sort(nums, 7, sizeof(int), cmp);
    for (int i = 0; i < 7; i  )
        printf("%i ", nums[i]);
    return 0;
}
  

Ошибка в функции merge_sort() : второй рекурсивный вызов выполняется по неправильному базовому адресу:

 merge_sort(char_base   (num - s) * el_size, num - s, el_size, compar);
  

исправление с

 merge_sort(char_base   s * el_size, num - s, el_size, compar);
  

Обратите внимание, что в вашем коде есть и другие проблемы:

• функции сравнения имеют неправильные подписи, они должны принимать const void * аргументы.

• оба merge() и merge_sort() должны быть определены как void , поскольку они не возвращают никакого значения.

• CompareInt невозможно обрабатывать большие целочисленные значения, разница между которыми превышает INT_MAX , например , INT_MAX и INT_MIN . Это должно быть написано:

   int CompareInt(const void *a, const void *b) {
      int na = *(const int *)a;
      int nb = *(const int *)b;
      return (nb < na) - (na < nb);
  }
    

• вы должны напечатать a 'n' после чисел.

Вы также можете улучшить реализацию различными способами:

• если вы вычисляете s как (n 1) / 2 , вы можете использовать меньше памяти и иметь более простую и быструю реализацию, поскольку вам не понадобится second массив в merge функции.

• используя указатели, вы бы значительно сократили количество умножений.

Вот более простая реализация с той же семантикой:

 void merge(void *base, size_t num, size_t el_size, size_t size,
           int (*compar)(const void*, const void*)) {
    size_t split = size * el_size;
    char *first = malloc(split);
    char *p1 = memcpy(first, base, split);
    char *dest = base, *p2 = dest   split;
    size_t i = 0, j = size;
    while (i < size) {
        if (j == num || compar(p1, p2) <= 0) {
            for (size_t k = 0; k < el_size; k  )
                *dest   = *p1  ;
            i  ;
        } else {
            for (size_t k = 0; k < el_size; k  )
                *dest   = *p2  ;
            j  ;
        }
    }
    free(first);
}

void merge_sort(void *base, size_t num, size_t el_size,
                int (*compar)(const void*, const void*)) {
    if (num > 1) {
        size_t s = (num   1) / 2;
        char *char_base = base;
        merge_sort(char_base, s, el_size, compar);
        merge_sort(char_base   s * el_size, num - s, el_size, compar);
        merge(char_base, num, el_size, s, compar);
    }
}