I'm writing a quicksort algorithm for integers and I get a strange segfault error in srand functions. Here is the code from sort.h:
int distributePivot (int *a, int left, int pivot, int right) {
int i, j;
if (pivot != right)
swapInt(&pivot, &right);
i = left;
j = right - 1;
while (i < j) {
while (i < j && a[i] <= a[right])
i++;
while (j > i && a[j] >= a[right])
j--;
if (i < j)
swapInt(&a[i], &a[j]);
}
if (i < right)
swapInt(&a[i], &a[right]);
return i;
}
void intArrayQuickSort (int *a, int left, int right) {
int pivot;
if (left < right) {
pivot = rand() % (right - left +1) + left;
pivot = distributePivot(a, left, pivot, right);
intArrayQuickSort (a, left, pivot -1);
intArrayQuickSort (a, pivot, right);
}
}
And here is the calling from sort-test.c:
srand(time(NULL));
intArrayQuickSort(temp, 0, n - 1);
Where temp
is a pointer to integer.
And here is the error I get when i execute it in gdb:
Program received signal SIGSEGV, Segmentation fault.
0x00007ffff77e9884 in rand () from /lib64/libc.so.6
Can you please help me?
Thank you very much.
EDIT: This is the swapInt function:
void swapInt (int *a, int *b) {
int aux = *a;
*a = *b;
*b = aux;
}
There is an error in the program logic.
E.g.
in main
array = [1,2]
call intArrayQuickSort(array, 0, 1);// a:array, left:0, right:1
in intArrayQuickSort
pivot = 1 //provisional result of rand() % (right - left +1) + left;
call distributePivot(a, 0, 1, 1)
in distributePivot
not swap (pivot, right) because pivot == righit
i = 0 //left
j = 0 //right - 1
not execute while block because i == j
execute swap (a[i],a[right]) because i < right // 0 < 1
//a = [2, 1] //!!NG
return 0
//Already illegal state
in intArrayQuickSort
pivot = 0 ;//from return value : 0
call intArrayQuickSort (a, 0, -1);//left:0, pivot -1 :-1
no operation return
call intArrayQuickSort (a, 1, 1);//pivot + 1:1, right : 1
no operation return
in main
result:a = [2, 1] //NG!