Merge sort in C returns a list containing duplicates of the same 3-4 numbers. Other numbers are missing from sorted list

huangapple go评论60阅读模式
英文:

Merge sort in C returns a list containing duplicates of the same 3-4 numbers. Other numbers are missing from sorted list

问题

我正在尝试在C中实现一个基本的归并排序程序。然而,我不断地得到连续相同数字的多个实例,而其他数字完全被跳过。我使用了以下函数和主函数:

void merge_sort(int *arr, int left, int right){
    if (left < right){
        int mid = left + (right - left) / 2;

        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

void merge(int *arr, int left, int mid, int right){
    int length1 = mid - left + 1;
    int length2 = right - mid;
    int left_arr[length1];
    int right_arr[length2];

    int i, j;
    for (i = 0; i < length1; i++)
        left_arr[i] = arr[left + i];
    for (j = 0; j < length2; j++)
         right_arr[j] = arr[mid + 1 + j];

    i = 0;
    j = 0;
    int k = left;
    while (i < length1 && j < length2){
        if (left_arr[i] <= right_arr[j){ 
            arr[k] = left_arr[i]; 
            i++;
        }
        else{
            arr[k] = right_arr[j]; 
            j++;
        }
        k++;
    }
    while (j < length2){
        arr[k] = right_arr[j];
        j++;
        k++;
    }
}

void print_array(int array[], int length){
    for (int i = 0; i < length; i++)
        printf("%d ", array[i]);   
}

//MAIN FILE
#include <stdio.h> 
#include <stdlib.h>
#include "sorting.h"

#define ARR_LENGTH 8

int main(int argc, char *argv[]){
    int arr[ARR_LENGTH];
    if (argc != ARR_LENGTH + 1)
        printf("传递的参数过多或过少。");
    else{
        for (int i = 1; i <= ARR_LENGTH; i++)
            arr[i - 1] = strtod(argv[i], NULL);
        merge_sort(arr, 0, ARR_LENGTH - 1);
        print_array(arr, ARR_LENGTH);
    }
    return 0;
}

示例输入和输出:
输入: 6 5 4 3 2 1 8 9
输出: 1 2 3 4 5 6 8 9

英文:

I'm trying to implement a basic merge sort program in C. However, I keep getting multiple instances of the same numbers in a row, where as other numbers are completely skipped. I used the following functions and main

void merge_sort(int *arr, int left, int right){
if (left&lt;right){
int mid = left + (right-left)/2;
merge_sort(arr, left, mid);
merge_sort(arr, mid+1, right);
merge(arr, left, mid, right);
}
}
void merge(int *arr, int left, int mid, int right){
int lenght1 = mid - left + 1;
int lenght2 = right - mid;
int left_arr[lenght1];
int right_arr[lenght2];
int i, j;
for (i=0; i&lt;lenght1; i++)
left_arr[i] = arr[left+i];
for (j=0; j&lt;lenght2; j++)
right_arr[j] = arr[mid + 1 + j];
i=0;
j=0;
int k = left;
while(i&lt;lenght1 &amp;&amp; j&lt;lenght2){
if (left_arr[i]&lt;=right_arr[j]){ 
arr[k] = left_arr[i]; 
i++;
}
else{
arr[k] = right_arr[j]; 
j++;
}
k++;
}
while (j&lt;lenght2){
arr[k] = right_arr[j];
j++;
k++;
}
}
void print_array(int array[], int length){
for (int i=0; i&lt;length; i++)
printf(&quot;%d &quot;, array[i]);   
}
//MAIN FILE
#include &lt;stdio.h&gt; 
#include &lt;stdlib.h&gt;
#include &quot;sorting.h&quot;
#define ARR_LENGHT 8
int main(int argc, char *argv[]){
int arr[ARR_LENGHT];
if (argc!=ARR_LENGHT+1)
printf(&quot;Too many or too few arguments passed.&quot;);
else{
for (int i=1; i&lt;=ARR_LENGHT; i++)
arr[i-1]=strtod(argv[i], NULL);
merge_sort(arr, 0, ARR_LENGHT-1);
print_array(arr, ARR_LENGHT);
}
return 0;
}

example of input and output:
input: 6 5 4 3 2 1 8 9
output: 1 1 3 3 3 3 8 9

答案1

得分: 0

对于起始部分,不清楚为什么要使用设计用于解析双精度值的标准函数 strtod,而不是例如 strtol 或甚至 atoi

至于函数定义,除了函数 merge 中的这个 while 循环:

while (j < lenght2){
    arr[k] = right_arr[j];
    j++;
    k++;
}

你还需要添加一个 while 循环:

while (i < lenght1){
    arr[k] = left_arr[i];
    i++;
    k++;
}

也就是你将会有:

while (j < lenght2){
    arr[k] = right_arr[j];
    j++;
    k++;
}

while (i < lenght1){
    arr[k] = left_arr[i];
    i++;
    k++;
}

while 循环的顺序无关紧要。

另外,函数 merge 应该在函数 merge_sort 之前声明。

英文:

For starters it is unclear why you are using the standard function strtod that is designed to parse double values instead of for example strtol or even atoi.

As for the function definitions then apart from this while loop within the function merge

while (j&lt;lenght2){
arr[k] = right_arr[j];
j++;
k++;
}

you also need to add one more while loop

while (i&lt;lenght1){
arr[k] = left_arr[i];
i++;
k++;
}

That is you will have

while (j&lt;lenght2){
arr[k] = right_arr[j];
j++;
k++;
}
while (i&lt;lenght1){
arr[k] = left_arr[i];
i++;
k++;
}

The order of the while loops is unimportant.

Also the function merge should be declared before the function merge_sort.

huangapple
  • 本文由 发表于 2023年2月14日 05:12:51
  • 转载请务必保留本文链接:https://go.coder-hub.com/75441237.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定