C: Merge-Сорт массива с неравномерным количеством элементов

Question

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

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

Я пробовал ответы на вопросы, прежде чем публиковать их, но все остальные примеры включают в себя программы сортировки слияния с структурами, которые находятся за пределами того, что я узнал до сих пор. Вы увидите в коде, который я публикую ниже. Кроме того, полная программа включает в себя несколько других файлов, но я включил только файл mergesort.c и файл merge.c, который, как я был уверен моим профессором, - это единственные места, которые необходимо внести. Файл main отлично работает и отвечает только за заполнение массива и вызов функции mergesort. Если нужны другие файлы, дайте мне знать, и я опубликую их. Единственная причина, по которой у меня нет, это то, что мы используем оболочку Linux, и я не нашел практического способа скопировать и вставить код из оболочки в свою собственную операционную систему, и для ее выписки требуется некоторое время.

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

mergesort.c

#include <"mergesort.h"> 

void mergesort(int key[], int n) //key is the array, n is the size of key 
{ 
    int j, k, m, *w; 

    w = calloc(n, sizeof(int)); 
    assert(w != NULL); 

    for (k = 1; k < n; k *= 2) { 
     for (j = 0; j < n - k; j += 2 * k) { 
      merge(key + j, key + j + k, w + j, k, k); 
     } 
     for (j = 0; j < n; ++j) { 
      key[j] = w[j]; 
     } 
    } 
    free(w); 
} 

merge.c

#include "mergesort.h" 

void merge(int a[], int b[], int c[], int m, int n) { 
    int i = 0, j = 0, k = 0; 

    while (i < m && j < n) { 
     if (a[i] < b[j]) { 
      c[k++] = a[i++]; 
     } else { 
      c[k++] = b[j++]; 
     } 
    } 

    while (i < m) { 
     c[k++] = a[i++]; 
    } 
    while (j < n) { 
     c[k++] = b[j++]; 
    } 
} 

Answer 1

Ваш код имеет некоторые проблемы:

• включаемой директива препроцессора неверен, либо использовать #include "mergesort.h" или #include <mergesort.h>.

• Необходимо правильно вычислить размер массивов, переданных в merge(), чтобы он не читался за пределами последнего фрагмента. Как в настоящее время кодируется, n должен быть мощностью 2, чтобы избежать неопределенного поведения.

Вот исправленная версия mergesort.c для вашей цели:

#include "mergesort.h" 

void mergesort(int key[], int n) { 
    // key is the array, n is the number of elements 
    int i, j, k, m; 
    int *w; 

    // allocate the working array 
    w = calloc(n, sizeof(int)); 
    // abort the program on allocation failure 
    assert(w != NULL); 

    // for pairs of chunks of increasing sizes 
    for (k = 1; k < n; k *= 2) { 
     // as long as there are enough elements for a pair 
     for (j = 0; j + k < n; j = j + k + m) { 
      // compute the size of the second chunk: default to k 
      m = k; 
      if (j + k + m > n) { 
       // chunk is the last one, size may be smaller than k 
       m = n - j - k; 
      } 
      // merge adjacent chunks into the working array 
      merge(key + j, key + j + k, w + j, k, m); 
      // copy the resulting sorted list back to the key array 
      for (i = 0; i < k + m; i++) { 
       key[j + i] = w[j + i]; 
      } 
     } 
    } 
    free(w); 
} 

Вот некоторые дополнительные замечания по поводу этого упражнения, но вы не могли бы быть достаточно развиты и изменения API, вероятно, не допускается:

• Использование 2 различных исходных файлов кажется излишним. Подпрограмма merge является вспомогательной функцией, которая должна быть static. Он будет расширен встроенными современными компиляторами.

• Размеры массива должны быть переданы как size_t сразу после соответствующего указателя (для согласованности).

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

• Вы можете использовать начало рабочего массива для всех операций слияния. Это повышает эффективность кэширования.

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

#include "mergesort.h" 

static void merge(int a[], size_t m, int b[], size_t n, int c[]) { 
    size_t i = 0, j = 0, k = 0; 

    while (i < m && j < n) { 
     if (a[i] < b[j]) { 
      c[k++] = a[i++]; 
     } else { 
      c[k++] = b[j++]; 
     } 
    } 
    while (i < m) { 
     c[k++] = a[i++]; 
    } 
    while (j < n) { 
     c[k++] = b[j++]; 
    } 
} 

int mergesort(int key[], size_t n) { 
    // key is the array, n is the size of key 
    // return 0 for success, -1 for failure with error code in errno 
    size_t i, j, k, m; 
    int *w; 

    w = calloc(n, sizeof(int)); 
    if (w == NULL) 
     return -1; 

    for (k = 1; k < n; k *= 2) { 
     for (j = 0; j + k < n; j += k + m) { 
      m = k; 
      if (j + k + m > n) { 
       m = n - j - k; 
      } 
      merge(key + j, k, key + j + k, m, w + j); 
      // copy the sorted chunk back to the key array 
      for (i = 0; i < k + m; i++) { 
       key[j + i] = w[i]; 
      } 
     } 
    } 
    free(w); 
    return 0; 
} 

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

static void merge(int a[], size_t m, int b[], size_t n, int c[]) { 
    /* always called with m > 0 and n > 0 */ 
    for (size_t i = 0, j = 0, k = 0;;) { 
     if (a[i] < b[j]) { 
      c[k++] = a[i++]; 
      if (i == m) { 
       while (j < n) { 
        c[k++] = b[j++]; 
       } 
       break; 
      } 
     } else { 
      c[k++] = b[j++]; 
      if (j == n) { 
       while (i < m) { 
        c[k++] = a[i++]; 
       } 
       break; 
      } 
     } 
    } 
} 

Вы можете улучшить mergesort и merge следующими идеями:

• сравнивая последний элемент a и первый элемент b в merge позволяет значительное улучшение скорости на частично или полностью отсортированных массивов.

• merge может вернуть количество элементов для копирования назад, удалив все копии в отсортированном футляре.

• , скопировав левый кусок во временный массив и объединившись в массив key, вы можете уменьшить размер временного массива.

• Объединение сбалансированных размеров блоков, а не степеней 2, уменьшает общее количество сравнений для неэнергии 2-х размеров массива, но его проще реализовать с помощью рекурсивного подхода.

Answer 2

Таким образом, я обнаружил, от чего происходит ошибка сегментации. Если присмотреться к первой внутренней для петли в вашем слиянии:

 for(j = 0; j < n - k; j += 2 * k) 
     { 
      merge(key + j, key + j + k, w + j, k, k); 
     } 

вы заметите, что состояние не очень совпадает с тем, что вы даете функции слияния в качестве границ для ломтиков массив. Условие равно j < n - k, поэтому максимальное значение j равно n - k - 1. Но в аргументах вашего слияния второй сегмент массива, который вы передаете, начинается с key + j + k, и вы говорите, что он имеет размер k, поэтому вы попадаете в индекс j + k + k - 1, если вы замените свой j своим максимальным значением, вы получите n - k - 1 + k + k - 1 = n. Это означает, что вы сообщаете функцию слияния, которую он может использовать до индекса n. Поскольку размер ключа равен n, он не имеет индекса n. Итак, как вы должны переписать свое условие? Мы только что вычислили максимальный индекс, к которому будет обращаться слияние: j + k + k - 1. Таким образом, это означает, что вам просто нужно установить j + k + k - 1 < n как условие. это означает:

 for(j = 0; j <= n - (k*2); j += 2 * k) 
     { 
      merge(key + j, key + j + k, w + j, k, k); 
     } 

Теперь мы избавились от ошибок сегментации, можно перейти ко второй части: заставить его работать для всех размеров.Причина в том, что он работает только для размеров, которые имеют мощность 2 (даже не все четные размеры: попробуйте сортировать это [2, 3, 5, 6, 4, 1], как вы увидите) из-за вашего k. Это значение k, которое устанавливает размер срезов, которые будут объединены в цикле. k получает умноженное на 2 после каждого раунда, поэтому он будет получать размеры, равные 2! Когда это не сила 2, она просто проигнорирует часть, которая «превысит» силу 2 ... если вы понимаете, что я имею в виду? Прежде чем мы сделали это изменение, которое разрешило ошибку сегментации, оно просто попыталось бы это сделать, но с ошибкой по этой причине (и вернуть ошибку). Теперь нам нужно сделать так, чтобы он сортировал последний фрагмент, который он просто игнорирует. Я только скопирует-функцию сортировки слиянием, так как это единственное, что изменится:

void mergesort(int key[], int n) //key is the array, n is the size of key 
{ 
    int j, k, neglected, *w; 
    w = calloc(n, sizeof(int)); 
    assert(w != NULL); 

    for(k = 1; k < n; k *= 2){ 
     for(j = 0; j <= n - (k*2); j += 2 * k){ 
      merge(key + j, key + j + k, w + j, k, k); 
     } 

     //size of part that got neglected (if it could fully be divided in slices of 2*k, this will be 0) 
     neglected = n % (2*k); 

     //copy everything except the neglected part (if there was none, it will copy everything) 
     for(j = 0; j < n-neglected; ++j) { 
      key[j] = w[j]; 
     } 

     if(neglected != 0 && neglected < n){ //couldn't devide it fully in slices of 2*k ==> the last elements were left out! merge them together with the last merged slice 
      merge(key + n - (2*k) - neglected, key + n-neglected, w + n - (2*k) - neglected, 2*k, neglected); 
      for(j = n - (2*k) - neglected; j < n; ++j) { //copy the part we just merged 
       key[j] = w[j]; 
      } 
     } 

     for(j = 0; j < n; ++j) { 
      key[j] = w[j]; 
     } 
    } 
    free(w); 
} 

Кроме того, мой компилятор жалуется на переменную вы не были с помощью: m