Search code examples
csrand

quicksort for integers, segmentation fault in rand()


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;
}

Solution

  • 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!