c - 线程 1 : EXC_BAD_ACCESS (code=1, 地址=0x7ffeefc00000)

Question

我是 C 的新手，我正在从 coursera 学习算法，在这里我正在尝试实现 3 向快速排序，我知道我遇到了一个错误的内存错误，它发生在数组第一次排序之后.

我在这里附上我的代码和 coursera 讲师使用的 java 代码的页面，任何更改错误的建议将不胜感激。

#include <stdio.h>
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void quicksort(int arr[],int low, int high)
{
    if(high<=low)
    return;
    int lt = low;
    int gt = high;
    int pivot = low;
    int  i = low;
    while(i<=gt)
    {
        if(arr[i]==arr[pivot])
            i++;
        else if(arr[i]<arr[pivot])
        {
            swap(&arr[i],&arr[lt]);
            i++;
            lt++;
        }
        else
        {
            swap(&arr[i],&arr[gt]);
            gt++;
        }
    }
    quicksort(arr,low,lt-1);
    quicksort(arr,gt+1,high);
}
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main()
{
    int arr[] = {5,1,2,8,7,5,5,6,5,4,5,3,9,10};
    int n = sizeof(arr)/sizeof(arr[0]);
    quicksort(arr, 0, n-1);
    printf("Sorted array: ");
    printArray(arr,n);
    return 0;
}

我附上coursera讲师java代码的图片 Java code

Answer 1

I am encountering a bad memory error

你在 Java 代码中犯了一个错误

    else
    {
        swap(&arr[i],&arr[gt]);
        gt++;
    }

必须是

    else
    {
        swap(&arr[i],&arr[gt]);
        gt--;
    }

在修正、编译和执行之后:

pi@raspberrypi:/tmp $ gcc -g -pedantic -Wextra so.c
pi@raspberrypi:/tmp $ ./a.out
Sorted array: 1 5 2 5 3 4 5 5 5 7 6 8 9 10 

在 valgrind 下执行:

pi@raspberrypi:/tmp $ valgrind ./a.out
==16601== Memcheck, a memory error detector
==16601== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==16601== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==16601== Command: ./a.out
==16601== 
Sorted array: 1 5 2 5 3 4 5 5 5 7 6 8 9 10 
==16601== 
==16601== HEAP SUMMARY:
==16601==     in use at exit: 0 bytes in 0 blocks
==16601==   total heap usage: 1 allocs, 1 frees, 1,024 bytes allocated
==16601== 
==16601== All heap blocks were freed -- no leaks are possible
==16601== 
==16601== For counts of detected and suppressed errors, rerun with: -v
==16601== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 3)

所以现在没有无效的内存访问......但是排序不起作用，这是因为你没有遵循有关 v/pivot 的 Java 代码

您必须将 int pivot = low; 替换为 int pivot = arr[low];，当然还有其他地方 arr[pivot]通过pivot

在那之后:

pi@raspberrypi:/tmp $ gcc -g -pedantic -Wextra so.c
pi@raspberrypi:/tmp $ ./a.out
Sorted array: 1 2 3 4 5 5 5 5 5 6 7 8 9 10 

在 valgrind 下:

pi@raspberrypi:/tmp $ valgrind ./a.out
==16833== Memcheck, a memory error detector
==16833== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==16833== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==16833== Command: ./a.out
==16833== 
Sorted array: 1 2 3 4 5 5 5 5 5 6 7 8 9 10 
==16833== 
==16833== HEAP SUMMARY:
==16833==     in use at exit: 0 bytes in 0 blocks
==16833==   total heap usage: 1 allocs, 1 frees, 1,024 bytes allocated
==16833== 
==16833== All heap blocks were freed -- no leaks are possible
==16833== 
==16833== For counts of detected and suppressed errors, rerun with: -v
==16833== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 3)