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

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

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

Доброго времени суток! Коротко о проблеме. После ознакомления с кодом в Вики и на различных форумах я склепал свой. Но ошыбки мне починить не удалось Я создаю массив, инициализирую его и делаю процедуру mergesort(). Первый аргумент ето входной массив, за ним идет отсортированый, далее левая и правая граница. Собственно проблема в нем Помогите пожалуста! 
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void mergesort (int*, int*, int, int);
void main ()
{
    int* input;
    int* output = (int*) calloc (11 , sizeof(int));
    int i;
    int mas[] = {4, 2, 7, 5, 1, 0, 3, 6, 8, 9};
    input = mas;
    mergesort (input, output, 0, 9);
    for (i = 0; i < 10; i++)
    {
        printf ("%d ", output[i]); 
        printf ("%d \n", input[i]);
    }
    _getch();
}
void mergesort (int* input, int* output, int left, int right)
{
    if (right - left < 1)
        return;
    else 
    {
        int i;
        int l, r;
        int mid = (left + right) / 2;
        mergesort (input, output, left, mid);
        mergesort (input, output, mid + 1, right);
 
//      mergesort();
        l = left;
        r = mid + 1;
        /*for (i = left; i < right; i++)
        {
            /*if (r <= right || (l <= mid && input[l] <= input[r]))
                output[i] = input[l++];
            else
                output[i] = input[r++];*/
            i = left;
            int k;
            while ((l <= mid) && (r <= right))
            {
                if (input[l] <= input[r])
                    output[i++] = input[l++];
                else
                    output[i++] = input[r++];
            }
            if (l > mid)
                for (k = r; k <= right; k++)
                    output[i++] = input[k++];
            else for (k = l; k <= mid; k++)
                    output[i++] = input[k++];
            for (k = left; k < right; k++)
                input[k] = output[k];
//      }
    }
}
Скрин консоли после вывода массива:
Апдейт. Немного изменил код и вот что из етого получилось. Первый этап обработки исключения в "0x0028160f" в "diskret.exe": 0xC0000005: Нарушение прав доступа при чтении "0x001e0000". Необработанное исключение в "0x777415ee" в "diskret.exe": 0xC0000005: Нарушение прав доступа при чтении "0x001e0000". Программа "[4176] diskret.exe: Машинный код" завершилась с кодом -1073741819 (0xc0000005). 
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void mergesort (int*, int*, int, int);
void main ()
{
    int* input;
    int* output = (int*) calloc (11 , sizeof(int));
    int i;
    int mas[] = {4, 2, 7, 5, 1, 0, 3, 6, 8, 9};
    input = mas;
    mergesort (input, output, 0, 9);
    for (i = 0; i < 10; i++)
    {
        printf ("%d ", output[i]); 
        printf ("%d \n", input[i]);
    }
    _getch();
}
void mergesort (int* input, int* output, int left, int right)
{
    if (right - left < 1)
        return;
    else 
    {
        int i;
        int l, r;
        int mid = (left + right) / 2;
        mergesort (input, output, left, mid);
        mergesort (input, output, mid + 1, right);
 
//      mergesort();
        l = left;
        r = mid + 1;
        for (i = left; i < right; i++)
        {
            if ((l < mid + 1 && r > right) || input[l] <= input[r])
                output[i] = input[l++];
            else
                output[i] = input[r++];
            i = left;
            int k;
            /*while ((l <= mid) && (r <= right))
            {
                if (input[l] <= input[r])
                    output[i++] = input[l++];
                else
                    output[i++] = input[r++];
            }
            if (l > mid)
                for (k = r; k <= right; k++)
                    output[i++] = input[k++];
            else for (k = l; k <= mid; k++)
                    output[i++] = input[k++];*/
            for (k = left; k < right; k++)
                input[k] = output[k];
 
        }
    }
}
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void mergesort (int*, int*, int, int);
void main ()
{
    int* input;
    int* output = (int*) calloc (11 , sizeof(int));
    int i;
    int mas[] = {4, 2, 7, 5, 1, 0, 3, 6, 8, 9};
    input = mas;
    mergesort (input, output, 0, 9);
    for (i = 0; i < 10; i++)
    {
        printf ("%d ", output[i]); 
        printf ("%d \n", input[i]);
    }
    _getch();
}
void mergesort (int* input, int* output, int left, int right)
{
    if (right - left < 1)
        return;
    else 
    {
        int i;
        int l, r;
        int mid = (left + right) / 2;
        mergesort (input, output, left, mid);
        mergesort (input, output, mid + 1, right);
 
//      mergesort();
        l = left;
        r = mid + 1;
/*      for (i = left; i < right; i++)
        {
            if ((l < mid + 1 && r > right) || input[l] <= input[r])
            {
                output[i] = input[l];
                l++;
            }
            else
            {
                output[i] = input[r];
                r++;
            }*/
            i = left;
            int k;
            while ((l <= mid) && (r <= right))
            {
                if (input[l] <= input[r])
                {
                    output[i++] = input[l];
                    l++;
                }
                else
                {
                    output[i++] = input[r++];
                    r++;
                }
            }
            if (l > mid)
                for (k = r; k <= right; k++)
                    output[i++] = input[k];
            else for (k = l; k <= mid; k++)
                    output[i++] = input[k];
            for (k = left; k < right; k++)
                input[k] = output[k];
    }
}
Исправил код.

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

textual
Листинг программы 
/* ANSI C 99 */
#include <stdio.h>
#include <string.h>
 
void dump(const int * arr, size_t count) {
    while ( count-- )
        printf("%d%c", *arr++, ( count ) ? ' ' : '\n');
}
 
void merge(const int * arrA, size_t cntA, const int * arrB, size_t cntB, int * arrC) {
    if ( cntA ) {
        if ( cntB ) {
            if ( *arrB < *arrA ) {
                *arrC++ = *arrB++;
                --cntB;
            }
            else {
                *arrC++ = *arrA++;
                --cntA;
            }
            merge(arrA, cntA, arrB, cntB, arrC);
        }
        else {
            while ( cntA-- )
                *arrC++ = *arrA++;
        }
    }
    else {
        while ( cntB-- )
            *arrC++ = *arrB++;
    }
}
 
int * merge_sort(int * arr, size_t count) {
    if ( count > 1 ) {
        int buf[count];
        merge(merge_sort(arr, count / 2), count / 2, merge_sort(arr + count / 2, count - count / 2), count - count / 2, buf);
        return memcpy(arr, buf, sizeof(int) * count);
    }
    else
        return arr;
}
 
#define COUNT (10)
 
int main(void) {
    int arr[COUNT] = { 5, 3, 8, 0, 7, 9, 1, 2, 6, 4 };
    
    printf("Unsorted:\n");
    dump(arr, COUNT);
    printf("Sorted:\n");
    dump(merge_sort(arr, COUNT), COUNT);
    
    return 0;
}

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

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

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

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

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

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

5   голосов , оценка 3.4 из 5
Похожие ответы