英文:
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
.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论