current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Join the Stack Overflow Community
Stack Overflow is a community of 6.3 million programmers, just like you, helping each other.
Join them; it only takes a minute:
Sign up
up vote 3 down vote favorite

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;
    }
}**
share|improve this question
up vote 7 down vote accepted

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.

share|improve this answer
    
Ah, I see. Thanks man! – slyturtle Aug 5 '13 at 5:46
    
Any future code changes that allow j to go below -1 could also be stopped with something like j>-1. – R Hughes Aug 5 '13 at 5:51
up vote 4 down vote

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;});
share|improve this answer
1  
I just started learning c++ so creating your own functions I feel is more beneficial then just using another's. – slyturtle Aug 5 '13 at 5:52
    
@user2651901: If you are trying to learn C++ through creation of functions, it is fine; for all other purposes, it is wrong – Kyle_the_hacker Aug 5 '13 at 10:01
    
@user2651901: That was my point, in C++ it is almost required to use STL. Forgetting about it doesn't make any sense so while it is useful to learn syntax and semantic of the language, for everything else it should be avoided. – Jack Aug 5 '13 at 14:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.