1. ## Insertion Sort Help

Ok so I have to write insertion sort but every time I compile it and run it and enter numbers to sort i get some crazy errors.
here is an example, I entered :2 3 4 1 5 and I got this output 2 -2.70464e+303 1 3 4
Im so confused on what to do

Here is my code so far:
any advice/help would greatly be appreciated
Code:
```  #include<iostream>
using namespace std;

#define MAX_LIST_LEN  100

int main(void){

int    n,                    // list length
j,                    // loop control
L,                    // index of rightmost element in unsorted section
count;                    // Count comparisons
double temp,                 // temporary storage
list[MAX_LIST_LEN];   // array to be sorted

// Get values for n and list.
cout << "Enter list length (must be less than or equal to "
<< MAX_LIST_LEN << "): ";
cin  >> n;
cout << "Enter " << n << " numbers:" << endl;
for(j=0; j<n; j++){
cin >> list[j];
}

// perform InsertionSort algorithm on list

L=2;
while(L<=n)
{
j=L;
while(j>=2 && list[j]<list[j-1]){
temp = list[j];
list[j]=list[j-1];
list[j-1]=temp;
j--;
}
L = L+1;
}

// Print out sorted list.
for(j=0; j<n; j++){
cout << list[j] << " ";
}
cout << endl;

return(0);
}```

2. Code:
```while(L<=n)
{
j=L;
while(j>=2 && list[j]<list[j-1])
{
temp = list[j];
list[j]=list[j-1];
list[j-1]=temp;
j--;
}
L = L+1;
}```
In the sorting loop what happens when L == n? (in this case 5)

Does it use an element of the array you have not received input for? (and is full of random data because you did not init your variables.)

3. A good way to do some basic debugging is to add cout in to the loop and observe yourself what is being compared and read. If you're list is not holding the data you entered it might be a problem with cin >>, clearing it? Just a guess...

Add a small loop to echo out the list your sorting, before the while loop, did the input save in to the array correctly?

Code:
```for(j=0; j<n; j++){
cout << list[j];
}```
If so continue using cout to get output as the algorithm progresses. You can do some more convenient debugging if you're using Visual C++ or what ever, just read up on it for your IDE/tools.

4. Originally Posted by since
If you're list is not holding the data you entered it might be a problem with cin >>, clearing it? Just a guess....
The problem is the use of '>=' in the sortings while loop (as it allows the array to go OOB).

In this case the array has elements 0-4 (for a total of 5) but this logic error in the sorting loop allows the 6th element of the array to be sorted (index of 5).

The 6th element contains a random value (because the variables are not initialised) which is then sorted into the inputed values.

That is not all that is wrong but it will move the OP forward.

5. Why j>=2 ?
Don't items 0 and 1 also deserve to be swapped if necessary?

6. Originally Posted by iMalc
Why j>=2 ?
Don't items 0 and 1 also deserve to be swapped if necessary?
The OP appears to think arrays in C/C++ are one based.

By starting at index 2 they think they are accessing/sorting the first elements of the array (with j==2 and comparing with [j-1]) on the loops first run (which would be correct in VB for example).

7. Originally Posted by novacain
The OP appears to think arrays in C/C++ are one based.
One might think that, but both for loops are correct in their indexing.

8. Originally Posted by iMalc
One might think that, but both for loops are correct in their indexing.
Good point.

Which makes me wonder where the OP got the sorting code from.....

9. Odd code nevertheless, the issue is that the OP has hard coded L =2. Then sets j = L. Then they call

Code:
```...

j--; /*potential problem and will lead to list[j-1] going to a negative index */```