Написание сортировки слиянием на C без указателей

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

Вот мой код:

/* This code will take input for 10 integers given by the user
into an array, sort them with a recursive merge function
and print the updated array in ascending order. */

#include <stdio.h>
#define ARRSIZE 10

void merge_sort (int arr[], int temp[], int left, int right);
void merge (int arr[], int temp[], int left, int mid, int right);

int main (void){
    int arr[ARRSIZE], temp[ARRSIZE], left, right, i;

    printf("Enter 10 integers for an array:");
    for(i=0;i<ARRSIZE;i++){
        printf("\narray value %d:", i+1);
        scanf("%d", &arr[i]);
    }
    left = 0;
    right = ARRSIZE-1;

    merge_sort(arr, temp, left, right);

    printf("\nHere is your updated array:");
    printf("\n{");
    for(i=0;i<ARRSIZE;i++){
        printf("%d,", arr[i]);
    }
    printf("}");

    return 0;
}

void merge_sort (int arr[], int temp[], int left, int right){
    if(left<right){
        int mid = (right-left)/2;
        merge_sort(arr, temp, left, mid);
        merge_sort(arr, temp, mid+1, right);
        merge(arr, temp, left, mid, right);
    }
}

void merge (int arr[], int temp[], int left, int mid, int right){
    int i, j, tempi = 0;
    for(i=left, j=mid+1; i<=mid && j<=right ;){
        // mid+1 is the start of the right array
        if(arr[i]<arr[j] && i<=mid){
            temp[tempi] = arr[i];
            tempi++;
            i++;
        }
        else if(arr[i]>arr[j] && j<=right){
                temp[tempi] = arr[j];
                tempi++;
                j++;
             }
    }
    for(i=0,j=right; i<=j; i++){
        arr[i] = temp[i];
    }
}

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


person Zelmec    schedule 18.02.2013    source источник
comment
на какой линии ошибка seg?   -  person Mitch Wheat    schedule 18.02.2013
comment
Моя оболочка не сообщает мне об этом, я набираю a.out, и она просто запускается. Я знаю, что ошибка где-то в моей функции слияния или слияния_сортировки.   -  person Zelmec    schedule 18.02.2013
comment
даже в отладочной сборке?   -  person Mitch Wheat    schedule 18.02.2013
comment
скомпилируйте с помощью gcc -o merge-sort -g merge-sort.c, затем запустите его под gdb: gdb ./merge-sort   -  person iain    schedule 18.02.2013
comment
Кстати, с технической точки зрения, когда вы передаете массив функции, он становится указателем.   -  person Karthik T    schedule 18.02.2013
comment
Вы говорите, что не используете указатели, но каждая из ваших функций merge и merge_sort принимает по два указателя в качестве аргументов.   -  person dreamlax    schedule 18.02.2013
comment
Я не знаю, как отлаживать, по крайней мере, в моей оболочке. У меня есть визуальная студия, но такие вещи, как необработанное исключение по адресу 0x775bb812 в сортировке слиянием.exe: 0xC0000005: место записи нарушения прав доступа 0x00230fdc. то, что всплывает, когда я пытаюсь запустить мою сборку. Все компилируется правильно, но я не могу найти эту проблему. Мне сказали, что ошибка сегментации, вероятно, лежит в одном из моих индексов массива.   -  person Zelmec    schedule 18.02.2013
comment
@KarthikT Я этого не знал: P   -  person Zelmec    schedule 18.02.2013
comment
@iain, что именно ты делаешь с -o и -g? Когда я компилирую, я обычно просто использую имя файла gcc -std=c89. и что там делает этот бит gdb? Потому что я в своей оболочке и перед каждой строкой теперь написано (gdb), но я не знаю, что теперь делать.   -  person Zelmec    schedule 18.02.2013
comment
@Zelmec -o устанавливает имя выходного файла, поэтому вместо a.out он будет называться сортировкой слиянием, а -g означает включение отладочной информации, чтобы вы могли запустить его в отладчике (например, gdb) и получить что-то полезное   -  person iain    schedule 18.02.2013
comment
@iain Большое спасибо! Я чувствую, что должен знать это :P Очевидно, мне еще многое предстоит узнать   -  person Zelmec    schedule 18.02.2013
comment
@Zelmec каждый должен с чего-то начинать. Изучение того, как делать даже несколько незначительных вещей в отладчике, безусловно, поможет вам при изучении C. Вот руководство для начинающих по gdb: web.eecs.umich.edu/~sugih/pointers/summary.html   -  person iain    schedule 18.02.2013
comment
Просто для начала попробуйте man gdb. Также поможет документация GDB.   -  person Caleb    schedule 18.02.2013
comment
@iain мой файл должен быть в виде исполняемого файла для отладки?   -  person Zelmec    schedule 18.02.2013
comment
@Zelmec да, потому что отладчик запускает исполняемый двоичный файл, а не просматривает исходный код.   -  person iain    schedule 18.02.2013
comment
@iain хорошо, спасибо большое! Я полагаю, мне просто нужно будет использовать Visual Studio, чтобы получить исполняемый файл. Нужно ли включать что-то еще?   -  person Zelmec    schedule 18.02.2013


Ответы (1)


Ну, я уже нашел одну тонкую ошибку: int mid = (right-left)/2; должно быть int mid = (left+right)/2;

Кроме того, какие потоки я нашел:

  1. Вы должны использовать tempi = left для простоты. Просто скопируйте входящую часть массива в соответствующую часть временного массива.

  2. В вашем цикле слияния вы можете поместить увеличивающийся темп внутри определения for:

    for( ...; ...; ++tempi)

  3. Внутри этого цикла вы проверяете границы, ПОСЛЕ вы прочитали значения из этого места. Это очень плохо. ОЧЕНЬ. Хотя здесь у вас не возникло никаких проблем только потому, что вы проверяете границы внутри определения for :) просто удалите их:

    for (i = left, j = 1 + mid; i <= mid && j <= right; ++tempi)
    {  
        if (arr[i] < arr[j])        temp[tempi] = arr[i++];
        else /* arr[j] <= arr[i] */ temp[tempi] = arr[j++];
    }
    
  4. Поскольку этот цикл завершается, когда любой подмассив достигает конца, вам нужно скопировать остальные элементы из другого подмассива в temp[]:

    if (i > mid) i = j; /* if we need to copy right subarray */
    for (; tempi <= right; ++tempi, ++i) temp[tempi] = arr[i];
    
  5. Итак, ваше копирование из временного массива будет выглядеть так

     for (i = left; i <= right; ++i) arr[i] = temp[i];
    
person MPogoda    schedule 18.02.2013
comment
Я все еще получаю ошибку, хотя. Я пытаюсь выяснить, есть ли у меня строка, которая заставляет меня индексировать за пределами моего массива - person Zelmec; 18.02.2013
comment
Ну, я нашел еще один способ улучшить слияние: когда основной цикл for завершен, у нас могут быть 2 ситуации: 1. Мы закончили левый подмассив. 2. Мы закончили подмассив. В первой ситуации нам не нужно копировать элементы справа от j в temp, а затем обратно в arr. Просто if (i > mid) right = tempi; и готово. Это изменение переменной right является локальным и может оптимизировать большую часть нашей работы :) - person MPogoda; 18.02.2013
comment
Подождите, как и 'if (i › mid) right = tempi;' заменить строку 'if (i › mid) i = j;'? и повлияет ли это на цикл for(; tempi ‹= right; ++tempi, ++i)? - person Zelmec; 18.02.2013
comment
ага. Это повлияет на эту строку и последнюю строку (обратное копирование из temp в arr). Если вы не можете понять это прямо сейчас, попробуйте понять первое решение. - person MPogoda; 18.02.2013
comment
да, я начинаю понимать ваше первое решение. Все первые изменения просто сокращают и оптимизируют мой код. Затем вы используете следующий цикл for, чтобы добавить оставшиеся значения arr к temp. Таким образом, установка tempi = right просто пропускает второй цикл for? - person Zelmec; 18.02.2013
comment
Да, он пропускает цикл for (; tempi <= right; ++tempi, ++i) temp[tempi] = arr[i]; и укорачивает последний цикл (если может). Просто нам не нужно копировать остальные элементы из правого подмассива. Они уже на своих местах - person MPogoda; 18.02.2013
comment
или установка права = tempi скорее. И тогда вам не нужно редактировать эти значения в массиве, потому что вы предполагаете, что они в правильном порядке, я вижу. Однако даже со всеми этими изменениями я все равно получаю ошибку сегментации..... - person Zelmec; 18.02.2013
comment
Вы изменили начальное значение tempi на left? - person MPogoda; 18.02.2013
comment
Да, я поместил это в объявление, где раньше было int... tempi = 0. Я не могу представить, что вызывает эту ошибку. - person Zelmec; 18.02.2013
comment
Можете показать свои тестовые данные? (ваш тестовый массив, который вызывает segfault) - person MPogoda; 18.02.2013
comment
Введите 10 целых чисел для массива: {3, 5, 7, 6, 8, 9, 10, 2, 1, 4}, за которым следует ошибка сегментации. Это вывод, который я получил - person Zelmec; 18.02.2013
comment
Ну, кажется, я что-то не так сказал выше, но я могу найти что угодно -_-. Вот сортировка слиянием, которая у меня работает. - person MPogoda; 18.02.2013
comment
Спасибо! Я ценю всю помощь любого человека! Вы были бесценны! - person Zelmec; 18.02.2013
comment
Кроме того, после сравнения моего кода с тем, который вы предоставили, я обнаружил, что просто забыл изменить свое среднее определение. - person Zelmec; 19.02.2013