这是我的代码,它一直运行到自由(右);更像是它完成了合并排序,然后出现了一个错误,有什么解决方案吗?
#include <stdio.h>
#include <stdlib.h>
void bubble_sort(int *l, int len) {
// Iterate through the list
for (int i = 0; i < len; i++) {
// Iterate through the list
for (int j = 0; j < len - 1; j++) {
// If the current element is greater than the next element, swap them
if (l[j] > l[j + 1]) {
// Swap the elements
int temp = l[j];
l[j] = l[j + 1];
l[j + 1] = temp;
// Print the list
for (int k = 0; k < len; k++) {
printf("%d ", l[k]);
}
printf("\n");
}
}
}
}
void selection_sort(int *l, int len) {
// Iterate through the list
for (int i = 0; i < len; i++) {
// Set the minimum index to the current index
int min_index = i;
// Iterate through the list
for (int j = i + 1; j < len; j++) {
// If the current element is less than the minimum element, set the minimum index to the current index
if (l[j] < l[min_index]) {
min_index = j;
}
}
// Swap the elements
int temp = l[i];
l[i] = l[min_index];
l[min_index] = temp;
// Print the list
for (int k = 0; k < len; k++) {
printf("%d ", l[k]);
}
printf("\n");
}
}
void insertion_sort(int *l, int len) {
// Iterate through the list
for (int i = 1; i < len; i++) {
// Set the current index to the current index
int j = i;
// While the current index is greater than 0 and the previous element is greater than the current element, swap them
while (j > 0 && l[j - 1] > l[j]) {
// Swap the elements
int temp = l[j - 1];
l[j - 1] = l[j];
l[j] = temp;
// Decrement the current index
j--;
}
// Print the list
for (int k = 0; k < len; k++) {
printf("%d ", l[k]);
}
printf("\n");
}
}
void merge(int *left, int left_len, int *right, int right_len) {
// Create a new list
int *result = malloc((left_len + right_len) * sizeof(int));
// Set the left index to 0 and the right index to 0
int i = 0;
int j = 0;
// While the left index is less than the length of the left list and the right index is less than the length of the right list
while (i < left_len && j < right_len) {
// If the left element is less than or equal to the right element, append the left element to the result list and increment the left index
if (left[i] <= right[j]) {
result[i + j] = left[i];
i++;
}
// Else, append the right element to the result list and increment the right index
else {
result[i + j] = right[j];
j++;
}
}
// Append the remaining elements in the left list to the result list
for (int k = i; k < left_len; k++) {
result[k + j] = left[k];
}
// Append the remaining elements in the right list to the result list
for (int k = j; k < right_len; k++) {
result[k + i] = right[k];
}
// Print the result list
for (int k = 0; k < left_len + right_len; k++) {
printf("%d ", result[k]);
}
printf("\n");
// Copy the result list to the original list
for (int k = 0; k < left_len + right_len; k++) {
left[k] = result[k];
}
// Free the result list
free(result);
}
void merge_sort(int *l, int len) {
// If the list is empty or has one element, return the list
if (len <= 1) {
return;
}
// Set the middle index to the length of the list divided by 2
int mid = len / 2;
// Set the left list to the first half of the list
int *left = malloc(mid * sizeof(int));
for (int i = 0; i < mid; i++) {
left[i] = l[i];
}
// Set the right list to the second half of the list
int *right = malloc((len - mid) * sizeof(int));
for (int i = mid; i < len; i++) {
right[i - mid] = l[i];
}
// Sort the left list
merge_sort(left, mid);
// Sort the right list
merge_sort(right, len - mid);
// Merge the left list and the right list
merge(left, mid, right, len - mid);
// Free the left list and the right list
free(left);
free(right); //Error ln 142, in picture below
}
int binary_search(int *l, int len, int target) {
// Set the low index to 0 and the high index to the length of the list minus 1
int low = 0;
int high = len - 1;
// While the low index is less than or equal to the high index
while (low <= high) {
// Set the middle index to the sum of the low index and the high index divided by 2
int mid = (low + high) / 2;
// If the middle element is equal to the target, return the middle index
if (l[mid] == target) {
return mid;
}
// Else if the middle element is less than the target, set the low index to the middle index plus 1
else if (l[mid] < target) {
low = mid + 1;
}
// Else, set the high index to the middle index minus 1
else {
high = mid - 1;
}
}
// If the target is not found, return -1
return -1;
}
int main() {
// Create a list
int l[] = {17, 36, 3, 10, 29, 42, 34, 8};
int len = sizeof(l) / sizeof(l[0]);
// Print the list
printf("Bubble Sort:\n");
// Sort the list using bubble sort
bubble_sort(l, len);
// Print the list
printf("Selection Sort:\n");
// Sort the list using selection sort
selection_sort(l, len);
// Print the list
printf("Insertion Sort:\n");
// Sort the list using insertion sort
insertion_sort(l, len);
// Print the list
printf("Merge Sort:\n");
// Sort the list using merge sort
merge_sort(l, len);
// Print the list
printf("Binary Search:\n");
// Search for the target in the list using binary search
printf("%d\n", binary_search(l, len, 42));
return 0;
}
所以我把代码从python改写成了C,在GDB中调试给了我截图中的错误。
GDB ss
我试着编辑函数本身来纠正内存问题,但它不起作用,所以我又回到了这个问题上,希望有人有更多的见解。
1条答案
按热度按时间vuv7lop31#
The segfault is triggered in
merge()
used bymerge_sort()
. Everything else is irrelevant.In
merge_sort()
you copy half of the input arrayl
into a newly allocated arrayleft
and the other half into another newly allocated arrayright
. Then recursivelymerge_sort()
those two halves which is fine. To combine the two halvesmerge()
is called where you incorrectly assume that the left and right arrays are allocated consecutively:The minimal fix is to make the assumption valid:
A even better resolution would be to:
main()
the task of duplicating the input array instead of doing that in your sort algorithm. This allowsmerge_sort()
to operate on the input array in-place (merge()
still uses the temporary array).right
array pointer argument tomerge()
. This documents that the left and right arrays are part of the the same array.merge()
andmerge_sort()
interface so the length argument is before the array argument so you can document how they relate.merge_sort()
and pass it tomerge_sort2()
andmerge2()
. That way you only haveO(n)
space overhead instead ofO(n*log(n))
. It is worth pointing out thatmalloc()
may require a kernel context switch which in turn would be the most expensive operation th themerge()
+merge_sort()
implementation. Doing 1 instead of n*log(n) calls tomalloc()
could be a significant (constant) factor in run-time. Sharing the temporary space, however, comes a cost as you would no longer be able to do the otherwise non-overlapping merge sorts in parallel.size_t
toint
for lengths. sizeof() in particular returns asize_t
value, and the cast to the (signed)int
will be problematic for sizes greater thanINTMAX
.memcpy()
instead of explicit loops when possible.memcpy()
is highly optimized, and succinctly expresses intent.sizeof()
. The former is robust if you change the type of the variable where the latter requires a code change if you didn't use atypedef
for the type.print()
function so you don't need the debug print statements in the sorting functions themselves.and it returns:
valgrind is happy: