Может ли кто-нибудь сказать мне, что не так с моей сортировкой слиянием?

Может ли кто-нибудь сказать мне, что не так с моей реализацией сортировки слиянием ниже? Я чешу голову в течение нескольких часов ..

void merge(int arr[], int low, int mid, int high)
{
    int i = 0;
    int j = 0;
    int k = 0;

    int buf1[1024];
    int buf1Length = mid - low + 1;

    int buf2[1024];
    int buf2Length = high - (mid + 1) + 1;

    for (i = low; i <= mid; i++)
    {
        buf1[j++] = arr[i];
    }

    for (i = mid + 1; i <= high; i++)
    {
        buf2[k++] = arr[i];
    }

    i = 0;
    j = 0;
    k = 0;

    while (j < buf1Length && k < buf2Length)
    {
        if (buf1[j] <= buf2[k])
        {
            arr[i++] = buf1[j++];
        }
        else
        {
            arr[i++] = buf2[k++];
        }
    }

    while (j < buf1Length)
        arr[i++] = buf1[j++];

    while (k < buf2Length)
        arr[i++] = buf2[k++];
}

void mergeSort(int arr[], int low, int high)
{
    int mid;

    if (low < high)
    {
        mid = (low + high) / 2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }
}

int main()
{
    int i;
    int arr[] = {6, 7, 2, 4, 9, 8};
    mergeSort(arr, 0, 5);

    printf("\n\n results: \n");
    for (i = 0; i < 6; i++)
    {
       printf("%d ", arr[i]);
    }
    printf("\n\n\n");

    return 0;
}

c mergesort
person Robert Hill    schedule 14.02.2011    source источник
comment
Если это домашнее задание, пожалуйста, убедитесь, что вы об этом прямо говорите.   -  person Adam Robinson    schedule 14.02.2011

Ответы (3)


arrow_upward
0
arrow_downward

Вы уверены, что хотите сделать это:

i = 0;
j = 0;
k = 0;

?

На первый взгляд, я думаю, что это должно быть:

i = low;
j = 0;
k = 0;
person Mikel    schedule 14.02.2011
comment
Ой ****! Как я это пропустил! Благодарю вас! - person Robert Hill; 14.02.2011
comment
Добро пожаловать. Пожалуйста, не забудьте принять ответ, если он работает. - person Mikel; 14.02.2011

arrow_upward
0
arrow_downward

Сортировка слиянием должна объединять отсортированные подпоследовательности:

a = 1,3,5
b = 2,4,6
c = merge(a, b) // C = 1,2,3,4,5,6

Вы не сортируете какую-либо подпоследовательность.

person vz0    schedule 14.02.2011

arrow_upward
0
arrow_downward

Проблема, без сомнения, в вашей функции merge().

Я бы предположил, что функция слияния будет выглядеть так (любые ошибки здесь оставлены читателю: X ... это не тестировалось и не готово, и его следует использовать только для концептуальных целей!):

/**
 * let mid be the last element of the first array
 * making mid + 1 the first element of the second
 */
merge(int[] arr, int low, int mid, int high) {

  int[] buff;
  int lowpos;
  int highpos;
  int i;

  buff = new int[high - low + 1];
  lowpos = low;
  highpos = mid + 1;

  // merge the two subarrays into the buffer
  for(i = 0; i < (high - low + 1); i++) {
    if(lowpos > mid)  buff[i] = arr[highpos++];

    else if(highpos > high) buff[i] = arr[lowpos++];

    else if(arr[lowpos] < arr[highpos] buff[i] = arr[lowpos++];

    else buff[i] = arr[highpos++];
  }

  // copy the buffer back into the main array
  for(i = 0; i < (high - low + 1) i++) arr[i+low] = buff[i];
}
person corsiKa    schedule 14.02.2011