CODEWITHSUNDEEP
c++algorithmsortingquicksort
Dex
Dex

Reputation: 398

How to count the number of arrays comparisions that occurred during Quick Sort?

I have written a C++ program which used to sort the array using Quicksort algorithm.

The program also counts the number of array element comparisons that occurred during sorting.

I know for sure the quicksort algorithm logic works but I am not sure if the number of comparisons being printed is the right one or not...

I would appreciate if anyone can tell me a mechanism to determine the number array element comparisons that can happen in a given input. Any example array with comparisons count will also help me test the correctness of my program.

Program Code:

using namespace std;

//Partition Logic
int* partion(int *a,int l, int r,int counter){
    //Initialization of parameters
    int* p = new int[2];
    int p_index=l;
    int pivot = a[r];

    //Loop through the array and check if a[i] is less than pivot
    for(int i=l;i<r;i++){
        if(a[i]<=pivot){
            counter++;
            swap(a[i],a[p_index]);
            counter++;
            p_index++;
        }
    }
    swap(a[p_index],a[r]);
    counter++;
    p[0] = p_index;
    p[1] = counter;
    return p;
}

//Recurse algorithm for QuickSort
int QuickSort(int *a,int l,int r,int counter){
    int count = counter;
    if(l<r){
        int *p = partion(a,l,r,count);
        int p_index = p[0];
        QuickSort(a,l,p_index-1,count);
        QuickSort(a,p_index+1,r,count);
        count = p[1];
    }
    return count;
}


int main(){

    //int a[] = {7,2,1,6,8,5,3,4};
    int a[] = {7,2,8};
    int counter = QuickSort(a,0,2,0);

    //Comparisions count
    cout << "Number of comparisions performed = "<<counter<<endl;

    //Printing the array
    for(int i=0;i<3;i++)
    cout << a[i]<< " ";

    system("PAUSE");
    return 0;
}

Upvotes: 1

Views: 913

Answers (1)

Jordi Vermeulen
Jordi Vermeulen

Reputation: 1198

This should be enough:

//Loop through the array and check if a[i] is less than pivot
for(int i=l;i<r;i++){
    if(a[i]<=pivot){
        swap(a[i],a[p_index]);
        p_index++;
    }
    counter++;
}
swap(a[p_index],a[r]);
p[0] = p_index;
p[1] = counter;
return p;

As mentioned in the comments, swapping is not a comparison. Also, you only increased counter when a[i]<=pivot was true, but even if it's false you still made a comparison.

On a side-note, however, the number of swaps obviously does affect performance, and is something that is also often considered when comparing sorting algorithms.

Upvotes: 1

Related Questions