Объединить сортировку в C, давая неправильные результаты

Question

Я написал программу сортировки слиянием, но я получил неправильные результаты.

Я видел другие программы, подобные этому, но они не помогают мне решить мою проблему. Я думаю, проблема в функции merge.

#include <stdio.h> 
#include "stdafx.h"   

#define Size 5 

//this is the array 
int arr[Size] = { 5, 4, 3, 2, 1 }; 
int sr[10]; 
void mergesort(int a[], int start, int end, int size); 
void merge(int a[], int start, int end, int size); 

int main(void) { 
    mergesort(arr, 0, 4, 5); 
    for (int i = 0; i < Size; i++) { 
     printf_s("%i", sr[i]); 
    } 
    printf_s("\n"); 
    return 0;   
} 

void mergesort(int a[], int start, int end, int size) { 
    if (size < 2) 
     return; 

    int s = size/2; 
    mergesort(a, start, (start + end)/2, s); 
    mergesort(a, (start + end)/2, end, s); 
    merge(a, start, end, s); 
} 

void merge(int a[], int start, int end, int size) { 
    int left = start; 
    int right = ((start + end)/2) + 1; 

    for (int i = 0; i < size; i++) { 
     if (left < (start + end)/2) { 
      if (right >= end) { 
       sr[i] = arr[left]; 
       left++; 
      } else 
      if (arr[left] < arr[right]) { 
       sr[i] = arr[left]; 
       left++; 
      } else { 
       sr[i] = arr[right]; 
       right++; 
      } 
     } else { 
      sr[i] = arr[right]; 
      right++; 
     } 
    } 
} 

Answer 1

(1) printf_s("%i",sr[i]); должно быть printf_s("%i ", arr[i]);

(2)

mergesort(a, start, (start + end)/2, s);//E.g index:{0,1,2,3,4}, start:0, (start + end)/2 : 2, s: 2, but 0(start),1,2(new end), this length is 3, not 2 
mergesort(a, (start + end)/2, end, s);//Duplicate start position and length should be size - s. E.g size:5, s:2, rest size is 3, not 2. 
merge(a, start, end, s);//s should be size 

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

mergesort(a, start, start + s - 1, s); 
mergesort(a, start + s, end, size - s); 
merge(a, start, end, size); 

(3) Изменение в соответствии с (2)
Изменить int right = ((start + end)/2) +1; на int right = start + size/2;.

(4) Добавить int sr[size]; // Избегайте использования глобальных переменных. Лучше использовать malloc. Например int *sr = malloc(size*sizeof(int));...free(sr);

(5)

if (left < (start+end)/2) 
{ 
    if (right >= end) 

должен быть

if (left < start + size/2) 
{ 
    if (right > end){//Should be >, not >= 

(6) Написать обратно в arr форме sr необходимо

---

Всего код:

#include <stdio.h> 
#include <stdlib.h> 

void mergesort(int a[], int start, int end, int size); 
void merge(int a[], int start, int end, int size); 

int main(void){ 
    int arr[] = {5,4,3,2,1}; 
    int size = sizeof(arr)/sizeof(*arr); 

    mergesort(arr, 0, size - 1, size); 
    for (int i = 0; i < size; i++){ 
     printf_s("%i ", arr[i]); 
    } 
    printf_s("\n"); 
    return 0; 
} 

void mergesort(int a[], int start, int end, int size){ 
    if (size < 2) 
     return; 

    int s = size/2; 
    mergesort(a, start, start + s - 1, s); 
    mergesort(a, start + s, end, size - s); 
    merge(a, start, end, size); 
} 
void merge(int a[], int start, int end, int size){ 
    int left = start; 
    int right = start + size/2; 
    int right_start = right; 

    int *sr = (int*)malloc(size*sizeof(*sr));//Cast(int*) is not necessary in C. 

    for (int i = 0; i < size; i++){ 
     if (left < right_start){ 
      if (right > end){ 
       sr[i] = a[left++]; 
      } else if (a[left] < a[right]) { 
       sr[i] = a[left++]; 
      } else { 
       sr[i] = a[right++]; 
      } 
     } else { 
      sr[i] = a[right++]; 
     } 
    } 
    for(int i = 0; i < size; ++i)//write back. 
     a[start + i] = sr[i]; 
    free(sr); 
} 

Answer 2

Ваш код неверен по нескольким причинам:

• mergesort делит диапазон на 2 половины размера size/2, что неправильно, если size даже не.

• недопустимые аргументы mergesort, только требуемые указатели и размер.

• функция merge получает значения из глобального массива arr вместо массива аргументов и сохраняют значения в глобальный временный массив sr, но не копирует его обратно в a массив.

Вот исправленная и упрощенная версия:

#include <stdio.h> 

void mergesort(int a[], int size); 

int main(void) { 
    int arr[] = { 5, 4, 3, 2, 1 }; 
    int size = sizeof(arr)/sizeof(arr[0]); 

    mergesort(arr, size); 
    for (int i = 0; i < size; i++) { 
     printf_s("%i ", arr[i]); 
    } 
    printf_s("\n"); 
    return 0;   
} 

void merge(int a[], int mid, int size) { 
    int sr[mid]; // temporary array for the left part 

    if (a[mid - 1] <= a[mid]) { // quick check for sorted case 
     return; 
    } 
    for (int i = 0; i < mid; i++) { // save left part 
     sr[i] = a[i]; 
    } 
    // merge into array `a`.  
    for (int i = 0, left = 0, right = mid; left < mid; i++) { 
     if (right == size || sr[left] <= a[right]) { 
      a[i] = sr[left++]; 
     } else { 
      a[i] = a[right++]; 
     } 
    } 
} 

void mergesort(int a[], int size) { 
    if (size >= 2) { 
     int mid = (size + 1)/2; // make left part no smaller than right part 
     mergesort(a, mid); 
     mergesort(a + mid, size - mid); 
     merge(a, mid, size); 
    } 
}