Блог

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

Проблема в том, что я получаю только 5 проходов с 6 элементами в массиве, а мой друг получает 13 проходов для тех же 6 цифр, наш студент почти идентичен (по нашему мнению). Мы вызываем одни и те же вещи и помещаем оператор printing passes в одно и то же место.

Я даю целые коды, а выходные данные:

1-й код:

 #include <stdio.h>

int size;

int merge(int arr[], int l, int m, int r) {
    int n1 = m - l   1;
    int n2 = r - m;
    int L[n1], R[n2];

    int i, j;
    for (i = 0; i < n1; i  )
        L[i] = arr[l   i];
    for (j = 0; j < n2; j  )
        R[j] = arr[m   1   j];

    i = 0, j = 0;
    int k = l;

    while (i < n1 amp;amp; j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i  ;
        } else {
            arr[k] = R[j];
            j  ;
        }
        k  ;
    }

    while (i < n1) {           
        arr[k] = L[i];
        i  , k  ;
    }
    while (j < n2) {           
        arr[k] = R[j];
        j  , k  ;
    }

    printf("n    pass:  ");                  // PASSES
    for (int x = 0; x < size; x  ) {        
        printf("%d  ", arr[x]);
    }
}

int mergesort(int arr[], int l, int r) {
    if (l < r) {
        int m = (l   r) / 2;
        mergesort(arr, l, m);
        mergesort(arr, m   1, r);
        merge(arr, l, m, r);
    }
}

int main() {
    printf("n    # MERGE SORT # nn");
    int i;
    int arr[20];

    printf("  Enter number of array elements: ");
    scanf("%d", amp;size);

    printf("  Enter array elements: ");
    for (i = 0; i < size; i  )
        scanf("%d", amp;arr[i]);

    mergesort(arr, 0, size - 1);

    printf("nn  Sorted array: ");
    for (i = 0; i < size; i  )
        printf("%d ", arr[i]);
    
    printf("nnn");
}
  

Вывод: OP

2-й код:

 #include <stdio.h>

int arr[50];
int n; 
int pass_count = 0;

void m_sort(int start, int end);
void merge(int start, int mid, int end);

int main() {
    int i;

    printf("nn______________MERGE SORT____________nn");

    printf("n  HOW MANY ELEMENTS WOULD YOU LIKE TO ENTER? ");
    scanf("%d", amp;n);
    printf("  Give Array: ");
    for (i = 0; i < n; i  )
        scanf("%d", amp;arr[i]);

    printf("nYOUR ARRAY: ");
    for (i = 0; i < n; i  ) 
        printf("%d  ", arr[i]);
    
    m_sort(0, n - 1);
    printf("nn");
}

void m_sort(int start, int end) {
    if (start < end) {
        int mid = (start   end) / 2;
        m_sort(0, mid);
        m_sort(mid   1, end);
        merge(start, mid, end);
    }
}

void merge(int start, int mid, int end) {
    int i, j, k;
    int n1, n2;
    n1 = mid - start   1;
    n2 = end - mid;
    int left_arr[n1], right_arr[n2];

    for (i = 0; i < n1; i  )
        left_arr[i] = arr[start   i];
    for (j = 0; j < n2; j  )
        right_arr[j] = arr[mid   1   j];
    
    i = 0;
    j = 0;
    k = start;
    
    while (i < n1 amp;amp; j < n2) {
        if (left_arr[i] <= right_arr[j]) {
            arr[k] = left_arr[i];
            i  ;
        } else {
            arr[k] = right_arr[j];
            j  ;
        }
        k  ;
    }

    while (i < n1) { 
        arr[k] = left_arr[i];
        i  ;
        k  ;
    }
    while (j < n2) {
        arr[k] = right_arr[j];
        j  ;
        k  ;
    }
    
    pass_count = pass_count   1;
    printf("nPASS %d: ", pass_count);    // PASSES
    //displaying passes
    for (i = 0; i < n; i  ) 
        printf("%d ", arr[i]);
    }
  

Вывод: OP

Заранее спасибо.

Первая программа верна.

Во второй программе обнаружена ошибка в m_sort() функции: рекурсивные вызовы используют неправильные значения индекса. Это должно быть:

 void m_sort(int start, int end) {
    if (start < end) {
        int mid = (start   end) / 2;
        m_sort(start, mid);         // instead of m_sort(0, mid)
        m_sort(mid   1, end);
        merge(start, mid, end);
    }
}
  

Также обратите внимание, что первый код использует локальные переменные, за исключением size того, что используется только для отображения фаз. Вторая программа использует слишком много глобальных переменных без уважительной причины.