CODEWITHSUNDEEP
carraysquicksortpartitioning
KittiCat
KittiCat

Reputation: 41

Arguments to Partition function for Quicksort

So I've been attempting to write a stack-based quicksort function, which calls a partition function. The header for partition() is as follows:

int partition(void **A, int n, void *pivot, int (cmp)(void *, void *));

where A is the array, n is the size of the array and pivot is the value of the pivot (not the index).

My current call to partition is: 

partition(&A[low_int], high_int + 1, A[low_int+(high_int-low_int)/2], cmp)

Above, my values for low and high are the classic 'l' and 'h' used in iterative quicksort, where l begins as the lowest index (and h the highest). These values then change as the function continues.

I'll post my partition function below:

int 
partition(void **A, int n, void *pivot, int (cmp)(void *, void *)) {
    int k;

    int i = 0;
    for (int j = 0; j <= n-2; j++) {
        if (cmp(A[j], pivot) <= 0) {
            i++;
            swap(A, i, j);
        }
    }
    swap(A, i+1, n-1);
    k = i + 2;
    return k; //k is the first value after the pivot in partitioned A

}

My problem is deciding on the inputs for my call to partition(). For the first argument, I've chose &A[low_int], as I'm not using a "left" as one of my inputs and therefore am trying to create a pointer to essentially start my array later. The third argument if for pivot, where I've been trying to select an element within that range, but both this and argument 1 have been causing my code to either return an unsorted array or run infinitely.

Could I please get some help here with what I've done wrong and how to fix it?

I've tried to include all relevant code, but please let me know if I've missed anything important or if anything I've written is unclear, or you need more info. Thank you

Upvotes: 0

Views: 449

Answers (1)

juhist
juhist

Reputation: 4314

Consider what happens if low_int is 1000 and high_int is 2000 and the array ends at 2000. Now you give it the array B = &A[1000] and the value 2001. The value of 2001 causes it to access the element B[2001-1] = B[2000] = A[3000]. It's accessing the array out of bounds.

Shouldn't you use something like high_int - low_int + 1 for the second argument? Note: I haven't verified that your code doesn't have off-by-one errors with the argument high_int - low_int + 1 but anyway it seems to me that you should be substracting low_int from high_int.

Another option would be to give it A, low_int and high_int.

Upvotes: 1

Related Questions