英文:
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<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<lenght1; i++)
left_arr[i] = arr[left+i];
for (j=0; j<lenght2; j++)
right_arr[j] = arr[mid + 1 + j];
i=0;
j=0;
int k = left;
while(i<lenght1 && j<lenght2){
if (left_arr[i]<=right_arr[j]){
arr[k] = left_arr[i];
i++;
}
else{
arr[k] = right_arr[j];
j++;
}
k++;
}
while (j<lenght2){
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_LENGHT 8
int main(int argc, char *argv[]){
int arr[ARR_LENGHT];
if (argc!=ARR_LENGHT+1)
printf("Too many or too few arguments passed.");
else{
for (int i=1; i<=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<lenght2){
arr[k] = right_arr[j];
j++;
k++;
}
you also need to add one more while loop
while (i<lenght1){
arr[k] = left_arr[i];
i++;
k++;
}
That is you will have
while (j<lenght2){
arr[k] = right_arr[j];
j++;
k++;
}
while (i<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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。


评论