Писане на сортиране чрез сливане в 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
Shell-ът ми не ми казва, въвеждам a.out и той просто се изпълнява. Знам обаче, че грешката е някъде в моята функция merge или merge_sort.   -  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 в merge sort.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, ще се нарича merge-sort, а -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:

    за (...; ...; ++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
или правилна настройка = темпове по-скоро. И тогава не е необходимо да редактирате тези стойности в масива, защото приемате, че са в правилния ред, разбирам. Въпреки това, дори с всички тези промени, все още получавам грешка при сегментиране..... - 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