Insertion Sort fails at a certain point

[Smartflight]

Hi,

I'm learning C/C++ at school and we have our vacations; thought I might do some programs on my own. I've landed at trouble with sorting numbers in a 1-D array at the time of insertion. It seems to work up to a certain point, after which it fails to work logically. I have tried to find my problem, but I couldn't and would appreciate some help here.

I have attached both the code and a sample output explaining my problem.

#include <iostream.h>
#define size 20

void main ()
{
	int arr[size], count=-1, j, temp, flag, pos;
	char ch;

	do {
		flag=0;
		
		cout<<"\nInput a number: ";
		cin>>temp;
	
		if (temp<arr[0])
		{
			for (j=count; j>=0; j--)
			arr[j+1]=arr[j];
			
			arr[0]=temp;
			flag=1; count++;
		}
			
		if (temp>arr[count])
		{
			arr[count+1]=temp;
			flag=1; count++;
		}
			
		if (flag==0)
		{
			for (j=1; j<=count; j++)
			{
				if (temp<arr[j])
				pos=j;
			}
			
			for (j=count; j>=pos; j--)
			arr[j+1]=arr[j];
			
			arr[pos]=temp;
			count++;
		}
		
		cout<<"\nThe list is: ";
		for (j=0; j<=count; j++)
		cout<<arr[j]<<" ";
		
		cout<<"\n\nEnter more numbers? (y/n)";
		cin>>ch;
	} while (ch=='y' || ch=='Y');
}

Input a number: 5

The list is: 5
//Goes to first position, OK

Enter more numbers? (y/n)y

Input a number: 2

The list is: 2 5
//Smaller than the smallest number, shifts the existing to right and goes to first position, OK

Enter more numbers? (y/n)y

Input a number: 3

The list is: 2 3 5
//3 is not smaller than 2, nor greater than 5, third condition executed, started search from 2nd position, 3 is smaller than (2+1) position, position becomes 2, number inserted, OK

Enter more numbers? (y/n)y

Input a number: 99

The list is: 2 3 5 99
//Larger than the largest number, inserted at last+1 position, OK

Enter more numbers? (y/n)y

Input a number: 123

The list is: 2 3 5 99 123
//Larger than the largest number, inserted at last+1 position, OK

Enter more numbers? (y/n)y

Input a number: 100

The list is: 2 3 5 99 100 123
//100 is not smaller than 2, nor greater than 123, third condition executed, started search from 2nd position, 100 is smaller than (5+1) position, position becomes 5, shifted 6th to the right, number inserted at 5, OK

Enter more numbers? (y/n)y

Input a number: 0

The list is: 0 2 3 5 99 100 123
//Smaller than the smallest, shifted all to right, added at 1st position

Enter more numbers? (y/n)y

Input a number: 1

The list is: 0 2 3 5 99 100 1 123
//Program fails, 1 is inserted at the second last position?

Any help?

Edit: Changed the condition for finding position under the third circumstance to

if (temp>arr[j-1] && temp<arr[j])

Seems to work perfectly now.
I would still like to know whether the code can be improved.

[nezachem]

The presence of flags, and special casing of certain conditions usually indicate that something is wrong. For example, on a very first insertion you compare temp with arr[0], which has a garbage value. If that comparison fail, the next comparison accesses arr[count], and count is -1. Welcome undefined behaviour.

Looking closely, you'd realize that all the work is really done in lines 32-42, with small modifications (count shall be initialized to 0 BTW):

for(pos = 0; (pos < count) && (temp > arr[pos]); pos++)
        ;
    for(i = count; i > pos; i--)
        arr[i] = arr[i - 1];
    arr[pos] = temp;
    count++;

Make sure you understand why count must be initialized to 0, and how your special cases are automatically handled here.

[Smartflight]

Thanks! That's really good piece of code!

Solved.