CODEWITHSUNDEEP
c++algorithmsortingquicksort
Moha the almighty camel
Moha the almighty camel

Reputation: 4453

Counting the number of comparisons in quicksort

I have a homework where I need to implement quicksort with three partition strategies and count the number of comparisons for each strategy.

for simplicity, we are asked to add m-1 to the count every time we do a recursive call on an array of length m.

my code is always returning a negative number and it is not an integer overflow issue.
I used long long int and I still have it, and there is no way the number of comparisons would grow that much, so there is something wrong with the way I am counting.

I tested the code on a 100000 element array using is_sorted after calling my implementation and it passed, so the the sorting is correct
here is my code:

long quick_sort (vector <int>& A, int l , int r){
    static  long count = 0;
    if ( r<= l)
        return 0;

    //partition
    int i = partition(A, l, r);

    //quicksort left
    int amount = ( ((i -1) -l) >= 0 ?
                            ((i-1) -l) :
                                    0);
    count += amount;
    quick_sort (A,l, i-1);

    //quicksort right
    amount = ((r - (i +1)) >= 0 ?
                        (r - (i +1)) :
                                  0);
    count += amount;
    quick_sort (A,i+1, r);

    return count;

}

Upvotes: 2

Views: 2084

Answers (2)

2501
2501

Reputation: 25752

Change your test value to hold correct expressions:

count += ( (i-1)-l >= 0 ? (i-1)-l : 0 )
quick_sort (A,l, i-1);

and

count += ( r-(i+1) >= 0 ? ...
quick_sort (A,i+1, r);

Upvotes: 2

Dwayne Towell
Dwayne Towell

Reputation: 8583

Your static variable is probably not being set to 0 when you expect it to. Make it a global variable.

Also, why are you doing the work when you make the recursive calls instead of when the call is made? It would be so much easier to do it one time instead of two.

Upvotes: 0

Related Questions