Блог

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

Проблема в том, что алгоритм выдает неверный результат. Пример:
ввод: (10, 5, 16, 2)
вывод: (2, 5, 5, 10)

 #include <stdio.h>

void mergesort(int A[], int l, int r);
void merge(int A[], int l, int q, int r);

int main() {
    int n;
    scanf("%d", amp;n);
    int tablica[n];

    for (int i = 0; i < n; i  )
        scanf("%d", amp;tablica[i]);

    mergesort(tablica, 0, n - 1);

    for (int i = 0; i < n; i  )
        printf("%d ", tablica[i]);

    return 0;
}

void mergesort(int A[], int l, int r) {
    if (l < r) {
        int q = (l   r) / 2;
        mergesort(A, l, q);
        mergesort(A, q   1, r);
        merge(A, l, q, r);
    }
}

void merge(int A[], int l, int q, int r) {
    int n = q - l   1;
    int m = r - q;

    int B[n];
    int C[m];

    for (int i = 0; i < n; i  )
        B[i] = A[i];

    for (int i = 0; i < m; i  )
        C[i] = A[q   1   i];

    int i = 0;
    int j = 0;

    for (int k = l; k <= r; k  ) {
        if (B[i] <= C[j] || j >= m) {
            A[k] = B[i];
            i  ;
        } else {
            A[k] = C[j];
            j  ;
        }
    }
}
 

Не зная, что именно не работает (не компилируется ли оно? Вы получаете неверный вывод для некоторых входных данных?) трудно помочь. Здесь как минимум одна ошибка:

 if(B[i] <= C[j] || j >= m)
 

Должно быть

 if(j >= m || i < n amp;amp; B[i] <= C[j])
 

Важно проверить j >= m , прежде чем проверять неравенство, и добавить i < n проверку.

Без последнего, как только вы полностью используете B массив, B[i] он выйдет за границы массива, и вы получите неопределенное поведение.

Без первого раза j >= m условие B[i] <= C[j] будет проверяться ранее j >= m , также вызывая неопределенное поведение.

ОБНОВЛЕНИЕ: в приведенном вами фактическом примере вторая ошибка сводится к замене B[i] = A[i] на B[i] = A[l i] . С этими двумя изменениями приведенный вами пример работает.

Функция merge имеет несколько ошибок.

Например, размер массива C должен вычисляться как

 int m = r - q   1;
 

вместо

 int m = r - q;
 

Вместо этого цикла for

 for(int i = 0; i < n; i  )
    B[i] = A[i];
 

вы должны написать

 for(int i = 0; i < n; i  )
    B[i] = A[l   i];
 

Этот оператор if

 if(B[i] <= C[j] || j >= m)
 

может привести к неопределенному поведению, поскольку нет проверки достоверности используемых индексов i и j, принадлежат ли они допустимым диапазонам.

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

 #include <stdio.h>

void merge( int a[], size_t left, size_t middle, size_t right )
{
    size_t n1 = middle - left;
    size_t n2 = right - middle;
    int a1[n1];
    int a2[n2];
    
    for ( size_t i = 0; i < n1; i   )
    {
        a1[i] = a[left   i];
    }
    
    for ( size_t i = 0; i < n2; i   )
    {
        a2[i] = a[middle   i];
    }
    
    size_t i = left, i1 = 0, i2 = 0;
    
    while ( i1 < n1 amp;amp; i2 < n2 )
    {
        a[i  ] = a2[i2] < a1[i1] ? a2[i2  ] : a1[i1  ];
    }
    
    while ( i1 < n1 ) a[i  ] = a1[i1  ];
    while ( i2 < n2 ) a[i  ] = a2[i2  ];
}

void mergesort( int a[], size_t left, size_t right )
{
    if ( left   1 < right )
    {
        size_t middle = ( left   right ) / 2;
        mergesort( a, left, middle );
        mergesort( a, middle, right );
        merge( a, left, middle, right );
    }       
}

int main(void) 
{
    size_t n;
    
    if ( scanf( "%zu", amp;n ) == 1 amp;amp; n != 0 )
    {
        int a[n];
        
        for ( size_t i = 0; i < n; i   ) scanf( "%d", a   i );
    
        mergesort( a, 0, n );
        
        for ( size_t i = 0; i < n; i   )
        {
            printf( "%d ", a[i] );
        }
        
        putchar( 'n' );
    }
    
    return 0;
}
 

Если входные данные

 4
10 5 16 2
 

тогда результат будет

 2 5 10 16
 

В merge функции есть ошибка:

if (B[i] <= C[j] || j >= m) обращается B[i] к и C[j] перед тестированием, если i и j находятся ниже их соответствующих границ. Тест должен быть:

     if (i < n amp;amp; (j >= m || B[i] <= C[j])) {
        A[k] = B[i  ];
    } else {
        A[k] = C[j  ];
    }
 

Обратите также внимание на эти замечания:

• вам не нужно сохранять вторую половину массива, потому что его элементы копируются до того, как они будут перезаписаны.
• in void mergesort(int A[], int l, int r) r следует исключить, чтобы избежать путаницы и ошибок 1 / -1 корректировок.
• аналогично, в void merge(int A[], int l, int q, int r) , q должно быть начало второй половины и r индекс элемента после конца среза.
• l выглядит до смешения похожим на 1

Вот измененная версия:

 #include <stdio.h>

void mergesort(int A[], int low, int high);
void merge(int A[], int low, int mid, int high);

int main() {
    int n;
    if (scanf("%d", amp;n) != 1 || n <= 0)
        return 1;

    int tablica[n];

    for (int i = 0; i < n; i  ) {
       if (scanf("%d", amp;tablica[i]) != 1)
           return 1;
    }
    mergesort(tablica, 0, n);

    for (int i = 0; i < n; i  )
        printf("%d ", tablica[i]);
    printf("n");
    return 0;
}

void mergesort(int A[], int low, int high) {
    if (high - low >= 2) {
        int mid = low   (high - low) / 2;
        mergesort(A, low, mid);
        mergesort(A, mid, high);
        merge(A, low, mid, high);
    }
}

void merge(int A[], int low, int mid, int high) {
    int n = mid - low;
    int B[n];

    for (int i = 0; i < n; i  )
        B[i] = A[low   i];

    int i = 0;
    int j = mid;
    int k = low;

    while (i < n) {
        if (j >= high || B[i] <= A[j]) {
            A[k  ] = B[i  ];
        } else {
            A[k  ] = C[j  ];
        }
    }
}