C quicksort with const unsigned** input pointers-CodePudding

I am currently struggling with Pointers in C , especially with the input of following function:

/*
... there is an immutable array a of unsigned integers that we are not allowed to change
In order to sort this array, a second array b containing pointers to the individual
elements in a is created. We then sort the poiners in b based on the values of the pointed-to elements in a.

(d) implement the quicksort function which sorts an array of pointers as outlined above.
    Note that the parameters to this function are two pointers, one to the first element in b and   
    one to the first element past the end of b.
 */
// Sort the range of pointers [begin; end)
void quicksort(const unsigned** begin, const unsigned** end)
{
    //TODO
}

However, the Function is given const values, so is there any way to change the position of the input pointers? A common Quicksort algorithm relies on the swap function, I tried calling

void swap (const unsigned** a, const unsigned** b){
    const unsigned** temp = **a;
    **a = **b;
    **b = temp;
}

with

swap(begin, (end-1));

in the Quicksort Function. But that does not not work as the value for **a cannot be changed (Here, with the value **b), due to it being const. So how would I even be able to sort the input pointers if I cannot change their order?

CodePudding user response：

First of all, I know this stuff is really tricky when starting out with c/c and I had my fair share of confusion when I did. Therefore I will try to explain it the best way I can:

What you are trying to do in your swap function is changing the actual value of the integers behind the pointers by dereferencing two times and reassigning. You got an array of pointers which is basically a pointer to the first pointer and if you dereference that two times you end up at the actual integers, however you don't want that because this integer is constant.

Instead you want to end up at the pointers to the actual integers and swap those around. You can achieve that by dereferencing only once. If you try to reasign the pointer to change what it's pointing to, you can change the order of the array of pointers without ever touching the actual integers.

your swap function should look like this:

void swap(const unsigned int** a,const unsigned int** b) {
    const unsigned int* temp = *a;
    *a = *b;
    *b = temp;
}

and the code where you call it could look something like this:

const unsigned int sort_without_touching[] = { 1 , 2 };

const unsigned int* ptr_array[] = {&sort_without_touching[0],
    &sort_without_touching[1]};

//1 2
std::cout << *ptr_array[0] << " " << *ptr_array[1] << std::endl;

swap((ptr_array  0), (ptr_array  1));

//2 1
std::cout << *ptr_array[0] << " " << *ptr_array[1] << std::endl;