Member Avatar

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.

Recommended Answers

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.

Jump to Post

All 2 Replies

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.

commented: Great code! +1
Member Avatar

Thanks! That's really good piece of code!

Solved.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.20 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.