Написание сортировки слиянием в 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. Есть предложения?

1 2
function recursion mergesort

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];
2