Why does this simple function crash?

[Book]

Hello,

I wonder if you can tell me why this simple sorting function crashes..

void Sorting (int p[], int d) {
     int* O=new (nothrow) int[d], *V=new (nothrow) int[d];
     int i, k, j=1;
     if (O==0||V==0) {cout<<"MEMORY NOT ALLOCATED?"<<endl;
                     goto Q1;
                     }
     for (i=0; i<d;i++) {
                        O[i]=-1;
                        }
     if (p[1]>p[0]) {
                    O[0]=0;
                    O[1]=1;
                    }
     else           {
                    O[0]=1;
                    O[1]=0;
                    }
     for (i=2;i<d;i++) {
                       if (p[i]>p[j]) {
                                      O[j]=i;
                                      j++;
                                      }
                       else           {
                                      k=j;
                                      while (p[O[k]]>p[i]) {
                                                           O[k+1]=O[k];
                                                           k--;
                                                           }
                                      O[k]=i;
                                      j++;
                                      }
                       }
     for (i=0;i<d;i++) {
                       V[i]=p[O[i]];
                       }
     for (i=0;i<d;i++) {
                       p[i]=V[i];
                       }
  Q1:i=0;
}

p is the array to be sorted and d is the number of its elements. O[] is used to hold the number of the element that should be occupying that position, (for example if O[1]=5, then p[5] should be p[1] in order for the array to get sorted), and V is the sorted array, which is then copied to p.
Whenever I run this function it crashes, and I can't figure out why.

My compiler is bloodshed dev C++ 4.9.9.2 version.

[ropez]

I think the best first step to finding the bug is to simplify the code as much as possible. In the large loop, I think the variable j is redundant, because it's always equal to i-1. Removing it will make it easier to find the problem.

Second, both i, j and k is not needed outside the scopes where they are used. You should try to have them declared in the closest scope possible. This means:

// Remove this line:
int i, k, j = 1;
// Change the for loops to:
for (int i = ...
// Declare k where you first need it:
int k = i - 1;
// Remove j entirely 

Doing these changes helps me figure out your code, and understanding what you're trying to do. It is basically the well known algorithm called insertion sort. Instead of sorting the array in place, you sort an array of references (O) to the original array, and you need a third array to temporary save your sorted array, so that you don't overwrite anything. You should know that it is possible to do the same thing with only one array. You simply have to do everything you do with O with p instead in the large loop.

Now to the actual problem: what if p[i] is the smallest value in the array in the inner while loop? You should try changing it to:

while (p[O[k]]>p[i] && k > 0)

I have a couple of other comments for you:
I don't like the (nothrow) and error handling using goto. You basically disable the much better error handling in C++, and go back to using old fashioned C code. If you really need to handle memory problems with NOT sorting the array (you will probably crash anyway), you should use a try...catch block, which is exactly what you simulate using the goto.

I don't like your indenting. You should stick with what's commonly used, and don't try to be overcreative. Get an editor with support for automatic indenting, and don't try to reinvent the wheel.

If you really only need to implement this sorting algorithm, you should do a search for insertion sort, and find examples of how to sort the array in place.

If you only need to sort an array, you should simply write:

std::sort(array, array + d);

But of course it's more interesting to implement it yourself, and you learn a lot in the process.

I wish you good luck.

[Book]

while (p[O[k]]>p[i] && k > 0) Thanks for this correction. This has been causing all the trouble.
The thing is that I am new to C++ and I just really like to code algorithms that I make up, in order to get more used to it. I have made another sorting algorithm which works great, and it's 6 times faster (measured in C++ with the clock() function returning CPU ticks (I think)) than the bubble sort. I made this algorithm quite "out of hand", and didn't really test its validity (the && k>0 addition is necessary). Still it needs correction though.

The goto command was just to verify that the function can allocate the memory and it's not part of the main idea.

Also about declaring the variables only in the scope where they're needed, I don't do that for the only reason to have all the variables grouped together in the beggining of the program.

Also, I can't say I agree with your comments about trying to design new algorithms for stuff that have already been dealt with.

[Book]

OK, I have changed a few stuff that were wrong about this function:
got rid of the j variable
changed the "if (p[i]>p[j])" (line 19) to "if (p[i]>p[Q[i-1]])"
using Q instead of O (to avoid mistakes)
changed "while (p[Q[k]]>p[i])" to "while (p[O[k]]>p[i] && k >= 0) "
changed O[k]=i; (in the while loop) to "O[k+1]=i;"

So now the code looks like this:

void Sorting (int p[], int d) {
     int* Q=new int[d], *V=new int[d];
     int i, k;
     for (i=0;i<d;i++) {
                       Q[i]=-1;
                       }
     if (p[1]>p[0]) {
                    Q[0]=0;
                    Q[1]=1;
                    }
     else           {
                    Q[0]=1;
                    Q[1]=0;
                    }
     for (i=2;i<d;i++) {
                       if (p[i]>p[Q[i-1]]) {Q[i]=i;}
                       else {
                            k=i-1;
                            while (p[Q[k]]>p[i] && k>=0) {
                                                         Q[k+1]=Q[k];
                                                         k--;
                                                         }
                            Q[k+1]=i;
                            }
                       }
     for (i=0;i<d;i++) {
                       V[i]=p[Q[i]];
                       }
     for (i=0;i<d;i++) {
                       p[i]=V[i];
                       }
}

The problem is that now the function crashes again (for example for d==5 and p[]: 6,9,3,20,856)! I changed the while (p[O[k]]>p[i] && k >= 0) to while (p[O[k]]>p[i] && k > 0) and it doesn't crash (at least for that input) anymore but I can't understand why (I am assuming though that it's because of accessing out of array bounds memory, *just* like in the original situation)! I made the flow chart (if that's how it's called) and observed the values the variables take during runtime (not with any program or anything, just wrote them down) and variable k never gets below zero (Actually, it gets, but I never access below zero array indices because I'm using k+1). So what can the problem now be?

Using Dev C++ debugger, it prompted a window saying: "An access violation (Segmentation fault) raised in your program". I don't really know what that means but it points to the line where the while loop is located

[Nate879]

Why are you using one-letter function names? It would be much easier to see what your code is doing if you used better names. It would also be good to use much smaller indents. I find that using 4-character indents is easiest to use and understand.

[Book]

Well p[] is the original array to be sorted, Q[] is the array to hold the references, and V[] is the sorted version of p[]. Anyway, I was able to figure the problem out: I must change while (p[Q[k]]>p[i] && k>=0) to while (k>=0 && p[Q[k]]>p[i]) And now it doesn't crash anymore, and it works fine. It's not too fast though