Joaquim Verdasca Joaquim Verdasca - 27 days ago 6
C Question

Abort trap: 6 on Mac when trying to run program with quicksort

So I'm trying to run the following C program, and all I get when I run it is an error that says: Abort trap: 6. Any ideas why? This only happens when I run the quicksort algorithm, I think it was something to do with the recursion but it should work fine so I don't know whats going on.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_DIM 30

int partition(char**, int, int);
void quickSort(char**, int, int);

int main()
{
char **array;
array = (char**) malloc(6*sizeof(char*));
for(int i = 0; i < 6; i++)
{
array[i] = (char*) malloc(MAX_DIM*sizeof(char));
}
strcpy(array[0], "ok");
strcpy(array[1], "bye");
strcpy(array[2], "then");
strcpy(array[3], "yeah");
strcpy(array[4], "lets");
strcpy(array[5], "go");
quickSort(array, 0, 5);
for(int i = 0; i < 6; i++)
{
printf("%s\n", array[i]);
}

return 0;
}

void quickSort(char **a, int l, int r)
{
int j;
if( l < r )
{
j = partition( a, l, r);
quickSort( a, l, j-1);
quickSort( a, j+1, r);
}
}

int partition(char **a, int l, int r) {
int i, j;
char pivot[MAX_DIM], t[MAX_DIM];
strcpy(pivot, a[l]);
i = l; j = r+1;
while(1)
{
do ++i; while( strcmp(a[i], pivot) <= 0 && i <= r );
do --j; while( strcmp(a[j],pivot) > 0);
if( i >= j ) break;
strcpy(t, a[i]); strcpy(a[i], a[j]); strcpy(a[j], t);
}

strcpy(t, a[l]); strcpy(a[l], a[j]); strcpy(a[j], t);
return j;
}

Answer

Logic Bug

(a && b) != (b && a)

in general, for C/C++. They are equal if and only if the evaluations of a and b are independent of each other.

In the specifications, there exists a short-circuit optimization so that if a is false, b will never be evaluated. Hence, the logical-and operation is not commutative, if expressions a and b are not independent of each other.

Your code is a perfect example of lack of independence between your expressions - ordering does matter.

Change:

do ++i; while( strcmp(a[i], pivot) <= 0 && i <= r );

To:

do ++i; while( i <= r && strcmp(a[i], pivot) <= 0 );

Output:

bye
go
lets
ok
then
yeah