Сортировка слиянием на массиве Int C++

Question

Я пытаюсь создать программу сортировки слиянием на массиве int, но у меня продолжают возникать проблемы с выполнением этой сортировки слиянием, она вызывает ошибку сегмента, но я не могу найти в этом ничего плохого. В void mergesort, когда я ставлю сначала <= last, то появляется ошибка сегмента, если нет, то 5 5 5 5 печатается.

#include <iostream>

 using namespace std;


void merge(int *arr, int size, int first, int middle, int last)
{
    int temp[size];
    for(int i = first; i<=last; i++)
    {
       temp[i] = arr[i];
    }
    int i=first, j=middle+1, k=0;
    while(i<=middle && j<=last)
    {
       if(temp[i] <= temp[j])
       {
          arr[k] = temp[i];
          i++;
       }
       else
       {
          arr[k]=temp[i];
          j++;
       }
       k++;
    }
    while(i<=middle)
    {
       arr[k]=temp[i];
       k++;
       i++;
    }
}

void mergesort(int *arr, int size, int first, int last)
{
    if(first<last)
    {
       int middle = ( first + last )/2;
       mergesort(arr,size,first,middle);
       mergesort(arr,size,middle+1,last);
       merge(arr,size,first,middle,last);
    }
}
int main()
{
    cout <<"Him";
    const int size = 10;
    int numbers [] = {5,10,1,6,2,9,3,8,7,4};
    mergesort(numbers,size,0,9);
    for( int i= 0; i<size; ++i)
    {
        cout << numbers[i] << " ";
    }
    return 0;
}

Answer 1

Есть (по крайней мере) две ошибки. Это:

else
{
   arr[k]=temp[i];                                          
   j++;
}

должно быть так:

else
{
   arr[k]=temp[j];                                          
   j++;
}

и это:

int i=first, j=middle+1, k=0;

должно быть так:

int i=first, j=middle+1, k=first;

В общем, вы должны научиться шагать по коду, по крайней мере, помещая диагностические операторы здесь и там. Как только вы это освоите, вы можете перейти к хорошему отладчику.

Answer 2

Стандартная библиотека уже реализует функцию, которая корректно объединяется: std::inplace_merge, Реализация адаптирована из этого более общего поста

void mergesort(int * first, int * last)
{
    std::ptrdiff_t N = std::distance(first, last);
    if (N <= 1) return;                   
    int * middle = std::next(first, N / 2);
    mergesort(first, middle); 
    mergesort(middle, last);  
    std::inplace_merge(first, middle, last); 
}

int main()
{
    cout <<"Him";
    const int size = 10;
    int numbers [] = {5,10,1,6,2,9,3,8,7,4};
    mergesort(numbers, numbers+size);
    for( int i= 0; i<size; ++i)
    {
        cout << numbers[i] << " ";
    }
    return 0;
}

Answer 3

Предложение 1:

Вместо этой строки:

int temp[size];

Если вам нужен массив динамического размера, используйте:

int temp = new int[size];

Затем, когда вы закончите с этим

delete[] temp;

Изменить: Как Нил предложил использовать std::vector, может быть более полезным, чем массивы в таких ситуациях (если вы можете использовать его).

Answer 4

Ваш код содержит 3 ошибки, также вы можете уменьшить длину кода, если это необходимо.

void merge(int *arr, int size, int first, int middle, int last)
{
    int temp[size];
    for(int i = first; i<=last; i++)
      temp[i] = arr[i];
    int i=first, j=middle+1, k=first; // 1st Change, Set k to first instead of 0
    while(i<=middle && j<=last)
    {
       if(temp[i] <= temp[j])
          arr[k++] = temp[i++];
       else
          arr[k++]=temp[j++]; // 2nd Change, use j instead of i
    }
    while(i<=middle)
       arr[k++]=temp[i++];
    while(j<=last)    // 3rd Change you missed this case
        arr[k++]=temp[j++];
}

Живой код