Pointer Array Sorting Algorithm in C++

Question

hoping I can get a little advice on a sorting method I made.

This is just a test for another program i am making and this test has a bug I can't figure out. The purpose of this code is to create a int pointer array and sort the pointers in that array by the contents of regular int array.

The bug is for my second for loop which doesn't allow me to use a j!=-1 therefore not allowing me to sort the first element of the array. Please help. Thanks!!

 //create array
 int c[8] = {3,1,5,7,8,2,6,4};
 //create pointer array
 int *newptr[8];
 for(int k = 0; k<8; k++)
 {
     newptr[k] = &c[k];
 }
//sort pointer array
for(int j = 0; j<8; j++)
{
    cout << "test1\n\n";
    cout << *newptr[j] << "and" << *newptr[j+1];
    for(;*newptr[j] < *newptr[j+1] && j!=0; j--) 
    //using j!=-1 doesn't work which causes me to not be able to sort the first element
    //in the array properly
    {
        cout<< "test2";
        int *temp;
        temp = newptr[j+1];
        newptr[j+1] = newptr[j];
        newptr[j] = temp;
    }
}**

Answer 1

Order matters.

Change

for(;*newptr[j] < *newptr[j+1] && j!=0; j--) 

to:

for(; j != -1 && *newptr[j] < *newptr[j+1]; j--) 

Presumably the bug is something that causes the code to crash. This happens because the expression in the for loop is evaluated left-to-right. So *newptr[j] is evaluated before checking if j != -1. So it's conceivable that, at some point, j is equal to -1 when *newptr[j] is evaluated, which is illegal.

Changing the order does make a difference for a second reason: short-circuit evaluation.

When evaluating two an expression made of two conditions A and B, C++ does not always need to evaluate both conditions.

For example in the statement

if (A && B) {
  //do something 
}

if A is evaluated to be false, then obviously A && B cannot evaluate to true regardless of what B evaluates to. So B's value is never even checked. So in your case, in the expression

j != -1 && *newptr[j] < *newptr[j+1]

if j != -1 is false, C++ will not need to evaluate the rest of the expression in order to know that the whole expression is false. So *newptr[j] never happens and you don't get the bug.

Answer 2

As pointed out by maditya the problem is that the expression tries to access an invalid index before checking the index itself but I see the question is tagged C++. Do you have any explicit reason to not use STL?

struct sorter {
  bool operator() (const int* i, const int* j) { return (*i<*j);}
};

int c[8] = {3,1,5,7,8,2,6,4};
int *newptr[8];
for(int k = 0; k<8; k++)
  newptr[k] = &c[k];

std::sort(newptr, newptr+8, sorter());

or even shorter in C++11:

int c[8] = {3,1,5,7,8,2,6,4};
int *newptr[8];
for(int k = 0; k<8; k++)
  newptr[k] = &c[k];
std::sort(newptr, newptr+8, [](const int *i, const int *j){return *i < *j;});