Vibhu Dubey Vibhu Dubey - 1 month ago 16
C++ Question

Error during implementation of quickSort algorithm in c++:- "error: cannot convert 'int*' to 'int**'....."

The full error is as follows:- "|error: cannot convert 'int*' to 'int**' for argument '1' to 'void quickSort(int**, int, int)'|"

MY whole code is below:

#include <iostream>

using namespace std;

int Partition (int *A[], int p, int r) {
int x = *A[r];
int i = p-1;
for (int j=0; j<=r; j++){
if(*A[j]<=x){
i++;
int save=*A[j];
*A[j] = *A[i];
*A[i] = save;
}
}
int save2=*A[i+1];
*A[i+1]=*A[r];
*A[r]=save2;
return (i+1);
}

void quickSort(int *A[], int p, int r) {
if (p<r){
int q = Partition(A, p, r);
quickSort(A, p, (q-1));
quickSort(A, (q+1), r);
}
}



int main() {
int RR[] = {2,8,7,1,3,5,6,4};
int y=sizeof(RR)/sizeof(int)-1;
cout << y << endl;
int *QQ = RR;
cout << *QQ << endl;
quickSort(QQ, 0, y);

return 0;
}


This is an implementation that I tried myself from a pseudo code. I'm new to programming so it would be a great help if you could illustrate a little of why this error occured.

Thanks in advanced.

Answer

The first thing I notice about the code is a whole lot of unneccessary pointer dereferencing. The contents of A will be changed without the need for additional pointers because Arrays decay to pointers (What is array decaying?) so A is treated as a pointer to the first array element and you are effectively passing the array by reference already.

Worse, int * A[] isn't a pointer to an array of int, it is an array of pointers to int. A very different thing. *A[0] does not return 2, it tries to use 2 as an address and return whatever happens to be in memory at address 2. This will almost certainly not be anything you want, or are allowed, to see so the program will do something unfortunate. Crash if you are lucky.

Instead, try

int Partition (int A[], int p, int r) {
    int x = A[r];
    int i = p-1;
    for (int j=0; j<=r; j++){
        if(A[j]<=x){
            i++;
            int save=A[j];
            A[j] = A[i];
            A[i] = save;
        }
    }
    int save2=A[i+1];
    A[i+1]=A[r];
    A[r]=save2;
    return (i+1);
}

void quickSort(int A[], int p, int r) {
    cout << p << ',' << r << endl; // Bonus: This will make the next bug really easy to see
    if (p<r){
    int q = Partition(A, p, r);
    quickSort(A, p, (q-1));
    quickSort(A, (q+1), r);
    }
}

Note the extra cout statement at the top of quickSort This will help you see the logic error in Partition. The program will crash due to a... wait for it! A Stack Overflow, but the cout will show you why.

Comments