MergeSort - исправить код - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Доброго времени суток! Коротко о проблеме. После ознакомления с кодом в Вики и на различных форумах я склепал свой. Но ошыбки мне починить не удалось Я создаю массив, инициализирую его и делаю процедуру mergesort(). Первый аргумент ето входной массив, за ним идет отсортированый, далее левая и правая граница. Собственно проблема в нем Помогите пожалуста!
Листинг программы 
  1. #include <stdio.h>
  2. #include <conio.h>
  3. #include <stdlib.h>
  4. void mergesort (int*, int*, int, int);
  5. void main ()
  6. {
  7.     int* input;
  8.     int* output = (int*) calloc (11 , sizeof(int));
  9.     int i;
  10.     int mas[] = {4, 2, 7, 5, 1, 0, 3, 6, 8, 9};
  11.     input = mas;
  12.     mergesort (input, output, 0, 9);
  13.     for (i = 0; i < 10; i++)
  14.     {
  15.         printf ("%d ", output[i]); 
  16.         printf ("%d \n", input[i]);
  17.     }
  18.     _getch();
  19. }
  20. void mergesort (int* input, int* output, int left, int right)
  21. {
  22.     if (right - left < 1)
  23.         return;
  24.     else 
  25.     {
  26.         int i;
  27.         int l, r;
  28.         int mid = (left + right) / 2;
  29.         mergesort (input, output, left, mid);
  30.         mergesort (input, output, mid + 1, right);
  31.  
  32. //      mergesort();
  33.         l = left;
  34.         r = mid + 1;
  35.         /*for (i = left; i < right; i++)
  36.         {
  37.             /*if (r <= right || (l <= mid && input[l] <= input[r]))
  38.                 output[i] = input[l++];
  39.             else
  40.                 output[i] = input[r++];*/
  41.             i = left;
  42.             int k;
  43.             while ((l <= mid) && (r <= right))
  44.             {
  45.                 if (input[l] <= input[r])
  46.                     output[i++] = input[l++];
  47.                 else
  48.                     output[i++] = input[r++];
  49.             }
  50.             if (l > mid)
  51.                 for (k = r; k <= right; k++)
  52.                     output[i++] = input[k++];
  53.             else for (k = l; k <= mid; k++)
  54.                     output[i++] = input[k++];
  55.             for (k = left; k < right; k++)
  56.                 input[k] = output[k];
  57. //      }
  58.     }
  59. }
Скрин консоли после вывода массива:
Апдейт. Немного изменил код и вот что из етого получилось. Первый этап обработки исключения в "0x0028160f" в "diskret.exe": 0xC0000005: Нарушение прав доступа при чтении "0x001e0000". Необработанное исключение в "0x777415ee" в "diskret.exe": 0xC0000005: Нарушение прав доступа при чтении "0x001e0000". Программа "[4176] diskret.exe: Машинный код" завершилась с кодом -1073741819 (0xc0000005).
Листинг программы 
  1. #include <stdio.h>
  2. #include <conio.h>
  3. #include <stdlib.h>
  4. void mergesort (int*, int*, int, int);
  5. void main ()
  6. {
  7.     int* input;
  8.     int* output = (int*) calloc (11 , sizeof(int));
  9.     int i;
  10.     int mas[] = {4, 2, 7, 5, 1, 0, 3, 6, 8, 9};
  11.     input = mas;
  12.     mergesort (input, output, 0, 9);
  13.     for (i = 0; i < 10; i++)
  14.     {
  15.         printf ("%d ", output[i]); 
  16.         printf ("%d \n", input[i]);
  17.     }
  18.     _getch();
  19. }
  20. void mergesort (int* input, int* output, int left, int right)
  21. {
  22.     if (right - left < 1)
  23.         return;
  24.     else 
  25.     {
  26.         int i;
  27.         int l, r;
  28.         int mid = (left + right) / 2;
  29.         mergesort (input, output, left, mid);
  30.         mergesort (input, output, mid + 1, right);
  31.  
  32. //      mergesort();
  33.         l = left;
  34.         r = mid + 1;
  35.         for (i = left; i < right; i++)
  36.         {
  37.             if ((l < mid + 1 && r > right) || input[l] <= input[r])
  38.                 output[i] = input[l++];
  39.             else
  40.                 output[i] = input[r++];
  41.             i = left;
  42.             int k;
  43.             /*while ((l <= mid) && (r <= right))
  44.             {
  45.                 if (input[l] <= input[r])
  46.                     output[i++] = input[l++];
  47.                 else
  48.                     output[i++] = input[r++];
  49.             }
  50.             if (l > mid)
  51.                 for (k = r; k <= right; k++)
  52.                     output[i++] = input[k++];
  53.             else for (k = l; k <= mid; k++)
  54.                     output[i++] = input[k++];*/
  55.             for (k = left; k < right; k++)
  56.                 input[k] = output[k];
  57.  
  58.         }
  59.     }
  60. }
Листинг программы 
  1. #include <stdio.h>
  2. #include <conio.h>
  3. #include <stdlib.h>
  4. void mergesort (int*, int*, int, int);
  5. void main ()
  6. {
  7.     int* input;
  8.     int* output = (int*) calloc (11 , sizeof(int));
  9.     int i;
  10.     int mas[] = {4, 2, 7, 5, 1, 0, 3, 6, 8, 9};
  11.     input = mas;
  12.     mergesort (input, output, 0, 9);
  13.     for (i = 0; i < 10; i++)
  14.     {
  15.         printf ("%d ", output[i]); 
  16.         printf ("%d \n", input[i]);
  17.     }
  18.     _getch();
  19. }
  20. void mergesort (int* input, int* output, int left, int right)
  21. {
  22.     if (right - left < 1)
  23.         return;
  24.     else 
  25.     {
  26.         int i;
  27.         int l, r;
  28.         int mid = (left + right) / 2;
  29.         mergesort (input, output, left, mid);
  30.         mergesort (input, output, mid + 1, right);
  31.  
  32. //      mergesort();
  33.         l = left;
  34.         r = mid + 1;
  35. /*      for (i = left; i < right; i++)
  36.         {
  37.             if ((l < mid + 1 && r > right) || input[l] <= input[r])
  38.             {
  39.                 output[i] = input[l];
  40.                 l++;
  41.             }
  42.             else
  43.             {
  44.                 output[i] = input[r];
  45.                 r++;
  46.             }*/
  47.             i = left;
  48.             int k;
  49.             while ((l <= mid) && (r <= right))
  50.             {
  51.                 if (input[l] <= input[r])
  52.                 {
  53.                     output[i++] = input[l];
  54.                     l++;
  55.                 }
  56.                 else
  57.                 {
  58.                     output[i++] = input[r++];
  59.                     r++;
  60.                 }
  61.             }
  62.             if (l > mid)
  63.                 for (k = r; k <= right; k++)
  64.                     output[i++] = input[k];
  65.             else for (k = l; k <= mid; k++)
  66.                     output[i++] = input[k];
  67.             for (k = left; k < right; k++)
  68.                 input[k] = output[k];
  69.     }
  70. }
Исправил код.

Решение задачи: «MergeSort - исправить код»

textual
Листинг программы 
  1. /* ANSI C 99 */
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. void dump(const int * arr, size_t count) {
  6.     while ( count-- )
  7.         printf("%d%c", *arr++, ( count ) ? ' ' : '\n');
  8. }
  9.  
  10. void merge(const int * arrA, size_t cntA, const int * arrB, size_t cntB, int * arrC) {
  11.     if ( cntA ) {
  12.         if ( cntB ) {
  13.             if ( *arrB < *arrA ) {
  14.                 *arrC++ = *arrB++;
  15.                 --cntB;
  16.             }
  17.             else {
  18.                 *arrC++ = *arrA++;
  19.                 --cntA;
  20.             }
  21.             merge(arrA, cntA, arrB, cntB, arrC);
  22.         }
  23.         else {
  24.             while ( cntA-- )
  25.                 *arrC++ = *arrA++;
  26.         }
  27.     }
  28.     else {
  29.         while ( cntB-- )
  30.             *arrC++ = *arrB++;
  31.     }
  32. }
  33.  
  34. int * merge_sort(int * arr, size_t count) {
  35.     if ( count > 1 ) {
  36.         int buf[count];
  37.         merge(merge_sort(arr, count / 2), count / 2, merge_sort(arr + count / 2, count - count / 2), count - count / 2, buf);
  38.         return memcpy(arr, buf, sizeof(int) * count);
  39.     }
  40.     else
  41.         return arr;
  42. }
  43.  
  44. #define COUNT (10)
  45.  
  46. int main(void) {
  47.     int arr[COUNT] = { 5, 3, 8, 0, 7, 9, 1, 2, 6, 4 };
  48.     
  49.     printf("Unsorted:\n");
  50.     dump(arr, COUNT);
  51.     printf("Sorted:\n");
  52.     dump(merge_sort(arr, COUNT), COUNT);
  53.     
  54.     return 0;
  55. }

Объяснение кода листинга программы

Код реализует алгоритм сортировки Merge Sort.

  1. В функции dump происходит вывод массива на экран. Принимает указатель на массив и количество элементов в массиве. Использует форматированный вывод для отделения элементов друг от друга пробелами или переносом строки в зависимости от количества оставшихся элементов.
  2. В функции merge происходит слияние двух отсортированных массивов в один. Принимает указатель на первый массив, количество элементов в первом массиве, указатель на второй массив, количество элементов во втором массиве и указатель на результирующий массив. Если в массивах остаются элементы, то рекурсивно вызывается функция merge для сортировки этих элементов. Если один из массивов пуст, то все оставшиеся элементы копируются в результирующий массив.
  3. В функции merge_sort происходит сортировка массива с помощью алгоритма Merge Sort. Принимает указатель на массив и количество элементов в массиве. Если количество элементов больше 1, то массив разбивается на две равные части, каждая из которых сортируется рекурсивно, затем эти части объединяются с помощью функции merge. Если количество элементов равно 1, то возвращается сам массив.
  4. В функции main создаётся тестовый массив, выводится его исходное состояние, затем вызывается функция merge_sort для сортировки массива и выводится отсортированный массив.

ИИ поможет Вам:

  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

5   голосов , оценка 3.4 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы