Mergesort в C не работает - PullRequest
Новая
       5

Mergesort в C не работает

0 голосов
/ 28 мая 2018

У меня есть реализация сортировки слиянием, которая не работает, и я не могу понять, почему.

Вот методы: 

    void merge_sort(int A[], int i, int j)
    {
       if(i<j)
       {
           int n = j-i+1;
           int k = n/2;

           merge_sort(A, i, i+k-1);
           merge_sort(A, i+k, j);
           merge(A, i, i+k, j);
       }
    }

И это метод слияния:

 void merge(int A[], int a, int b, int j)
{
    int* T = malloc(sizeof(int)*DIM);
    int c=0;
    int h=a;

    while(a<b && b<=j)
    {
    if(A[a] > A[b])
        T[c++] = A[a++];
    else
        T[c++] = A[b++];
    }
    while(a<b) T[c++] = A[a++];
    while(b<=j) T[c++] = A[b++];

    c=0;
    while(h<=j)
    A[h++] = T[c++];


}

Вот как я называю merge_sort: 

merge_sort(A, 0, DIM-1);

, где DIM - длина массива минус один.

Это вывод: 

5 2 4 6 8 9 7 1 3 10 
0 9
0 4
0 1
2 4
3 4
5 9
5 6
7 9
8 9
10 9 8 7 10 6 5 4 3 2

Первая половина отлично упорядочена, вторая половина также минус одна.Я не могу понять, в чем проблема.

1 Ответ

0 голосов
/ 28 мая 2018

Есть 2 проблемы с вашим кодом.

  1. Неправильные вычисления границ.
  2. У вас неверное условие while.

Неверный while здесь: 

while(a<b && b<=j)
{
if(A[a] > A[b])
    T[c++] = A[a++];
else
    T[c++] = A[b++];
}

В этом цикле вы увеличиваете b, пока он тоже в вашем состоянии, что повлияет на ваш цикл.

Вот ваш код, которыйЯ исправил (i включен в массив, а j исключен): 

void merge_sort(int A[], int i, int j)
{
   if(j-i>=2) // since j is excluded, this condition means that we have more than 1 member.
   {
       int k = (j+i)/2;

       merge_sort(A, i, k);
       merge_sort(A, k, j);
       merge(A, i, k, j);
   }
}

void merge(int A[], int a, int b, int j)
{
    int* T = malloc(sizeof(int)*DIM);
    int c=0;
    int h=a;
    int m = b;

    while(a<b && m<j) // b and j are excluded
    {
    if(A[a] > A[m])
        T[c++] = A[a++];
    else
        T[c++] = A[m++];
    }
    while(a<b) T[c++] = A[a++];
    while(m<j) T[c++] = A[m++];

    c=0;
    while(h<j)
    A[h++] = T[c++];
}

и запустил его с: 

merge_sort(A, 0, DIM);
...