CODEWITHSUNDEEP
c
Thanasis Papailiou
Thanasis Papailiou

Reputation: 1

Swaps and Comparisons in Quicksort

I think I have managed to figure the comparisons but I am trying to figure out how can I count the numbers of swaps. I have a problem with the value of swapcounter and the recursion. Any ideas? 

int quicksort (int nums[],int n,int left,int right){//quicksort takes an array, the leftmost index and the rightmost index

    int swapCounter=0;
    int i=left,j=right,temp;
    int comparisonCounter = 0;
    int pivot = nums[(left + right) / 2];
/* partition */
    while(i<=j){
    comparisonCounter++;
        while(nums[i]<=pivot)
            i++;
        while(nums[j]>pivot)
            j--;
        if(i<=j){
            temp=nums[i];
            nums[i]=nums[j];
            nums[j]=temp;
            i++;
            j--;
            swapCounter++;
        }
    }  

    /* recursion */
    if (left < j)
        comparisonCounter+=quicksort(nums,n, left, j);
    if (i < right)
        comparisonCounter+=quicksort(nums,n, i, right);

    printf("\nSwaps=%d\n",swapCounter);
    return comparisonCounter;
    }

Upvotes: 0

Views: 170

Answers (1)

unwind
unwind

Reputation: 400019

You can:

  • Make swapcounter global.
  • Make the function take a pointer to the variable.
  • Make the function call another function to do the counting, thus making maintaining the counter state Someone Else's problem.

Upvotes: 1

Related Questions