Алгоритм сортировки слияния в C не работает должным образом

Question

Я пытаюсь реализовать алгоритм сортировки слияния в C. Я понимаю, как должен функционировать алгоритм и логика, однако я сталкивался с некоторыми трудностями с прямой реализацией.

Я знаю, что есть много примеров для Merge Sorting online, и я также посмотрел на некоторые сообщения StackOverflow для подобных проблем. Тем не менее, я надеялся, что кто-то может помочь мне понять, почему мой код не работает правильно.

Мой код ниже:

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

// Function to Merge Arrays L and R into A 
// leftCount = number of elements in L 
// rightCount = number of elements in R 

void Merge(int *A,int *L,int leftCount, int *R, int rightCount) 
{ 

// i, to mark the index of subarray (L) 
// j, to mark the index of subarray (R) 
// k, to mark the index of subarray (A) 

int i = 0; 
int j = 0; 
int k = 0; 

while(i<leftCount && j<rightCount) 
{ 
    if(L[i] <= R[j]) 
    { 
     A[k++] = L[i++]; 
    } 
    else 
    { 
     A[k++] = R[j++]; 
    } 
} 
while(i<leftCount) 
{ 
    A[k++] = L[i++]; 
} 
while(j<rightCount) 
{ 
    A[k++] = R[j++]; 
} 
} 

// Recursive function to sort an array of integers 

void MergeSort(int *A, int n) 
{ 
int i; 
int mid; 
int *L; 
int *R; 
if (n<2) // Base condition 
    { 
    return; 
    } 

mid = n/2; // Find the mid index 
L = (int*)malloc(mid*sizeof(int)); 
R = (int*)malloc((n-mid)*sizeof(int)); 

for(i=0;i<mid;i++) // Creating left subarray 
    { 
    L[i] = A[i]; 
    } 
for(i=mid;i<n;i++) // Creating right subarray 
    { 
    R[i-mid] = A[i]; 
    } 

MergeSort(L,mid); 
MergeSort(R,n-mid); 
Merge(A,L,R,mid,n-mid); 
free(L); 
free(R); 
} 

int main() 
{ 

int A[] = {2,4,1,6,8,5,3,7}; 
int i; 
int numberofelements; 
numberofelements = sizeof(A)/sizeof(A[0]); 
MergeSort(A,8); 

for(int i = 0; i<8; i++) 
    { 
    printf("%d ",A[i]); 
    return 0; 
    } 
} 

После того как я запускаю этот код я, кажется, только чтобы получить выход «1», и не отсортированный массив. Я действительно надеялся, что кто-то сможет мне помочь.

Answer 1

Ваш Merge() подпись не совпадает, как вы вызываете его:

Подпись:

void Merge(int *A,int *L,int leftCount, int *R, int rightCount) 

Invokation:

Merge(A,L,R,mid,n-mid); 

Это приводит к неопределенному поведению, когда вы разбираете (и позже использование) а указатель (R) как целое число (leftCount) и целое число (mid) в качестве указателя (R).

Довольно, что ваш компилятор дал вам предупреждение об этом, убедитесь, что вы включите предупреждения, ваш компилятор обычно знает, что он говорит :)

Answer 2

Получить себе используется для компиляции с -Wall (если вы используете НКА). Если бы вы это сделали, вы бы увидели, что вы вызываете Merge() с неправильными аргументами. Должно быть:

Merge(A,L,mid,R,n-mid); 

Кроме того, вы не должны возвращаться из цикла, который печатает элементы массива. Вот почему вы видите только 1. Внимательно посмотрите на код: тело цикла возвращается безоговорочно с main(), поэтому он будет выполняться только один раз. Переместите return из петли:

for(i = 0; i<8; i++) 
{ 
    printf("%d ",A[i]); 
} 

return 0;