Поток 1: EXC_BAD_ACCESS (код = 1, адрес = 0x7ffeefc00000)

Question

Я новичок в C, и я изучаю алгоритмы на 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;
}

И я прилагаюизображение java-кода преподавателя Coursera Java-код

Answer 1

Я обнаружил ошибку неверной памяти

вы сделали ошибку из кода 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)

Так что теперь нет недопустимого доступа к памяти ... но сортировкане работает, это потому, что вы не следуете Java-коду, касающемуся v / pivot

Вы должны заменить 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)