Finding the 3 largest numbers of the five entered

So basically i have to enter 5 integers and then find the largest 3 of the 5 that were entered. I'm not sure exactly where I went wrong. The program will run but it gives the wrong answers everytime. If someone could help me out it would be greatly appreciated. Thanks

Code:

#include<stdio.h>

int main(void)

{
int n1, n2, n3, n4, n5;

printf("Enter 5 integer numbers\n");
scanf("%d,%d,%d,%d,%d", &n1, &n2, &n3, &n4, &n5);

printf("The largest 3 numbers of the 5 entered are:");

if ((n1>n2)&&(n1>n3)&&(n1>n4)&&(n1>n5))
printf("%d",n1);
else {if(n2>n3 && n2>n4 && n2>n5) 
printf("%d",n2);
else if(n3>n4 && n3>n5 && n3>n2)
printf("%d",n3);
else if(n4>n5 && n4>n2 && n4>n3)
printf("%d",n4);} 

if ((n2>n1)&&(n2>n3)&&(n2>n4)&&(n2>n5))
printf("%d",n2);
else {if (n1>n3 && n1>n4 && n1>n5) 
printf("%d",n1);
else if (n3>n4 && n3>n5 && n3>n1)
printf("%d",n3);
else if (n4>n5 && n4>n1 && n4>n3)
printf("%d",n4);}

if ((n3>n1)&&(n3>n2)&&(n3>n4)&&(n3>n5))
printf("%d",n3);
else {if (n1>n2 && n1>n4 && n1>n5) 
printf("%d",n1);
else if (n2>n4 && n2>n5 && n2>n1)
printf("%d",n2);
else if (n4>n5 && n4>n1 && n4>n2)
printf("%d",n4);}

if ((n4>n1)&&(n4>n2)&&(n4>n3)&&(n4>n5)) 
  printf("%d",n3);
else {if (n1>n2 && n1>n3 && n1>n5) 
printf("%d",n1);
else if (n2>n3 && n2>n5 && n2>n1)
printf("%d",n2);
else if (n3>n5 && n3>n1 && n3>n2)
printf("%d",n3);}


if ((n5>n1)&&(n5>n2)&&(n5>n3)&&(n5>n4))
printf("%d",n5);
else {if (n1>n2 && n1>n3 && n1>n4) 
printf("%d",n1);
else if (n2>n3 && n2>n4 && n2>n1)
printf("%d",n2);
else if (n3>n4 && n3>n1 && n3>n2)
printf("%d",n3);}

return (0);

}

Consider what will happen in a few months or so when your projects amount to several hundred or several thousand lines of code. Will you show up here and post the whole thing, explaining "train A and train B, train A coming from a small port in the south carrying agriculture, of which the fruit I place on top so it isn't squished. Then there is a communication system between the trains, which is used for various purposes. Neither of them are on the same track, so I don't know why they collide."

I could, and probably someone eventually will, come along and extract the relevant as opposed to irrelevant information. However, if it was really important to me to solve the problem (and by me, I think I now mean you), I might decide to do that myself, first, before I post anything.

But how! you ask. Well, that's a challenge itself -- but it might contain the solution! I will honestly admit that MOST of the questions I set out to ask on cboard get solved before they are posted -- that is, I actually sit there composing a "new thread", in the little "compose new thread" box, and by the time I get the question formulated as specifically as I can, MOST of the time I realize the answer. Honest. I can also honestly say that I have NEVER had to post a piece of code this long and I can tell you FOR A FACT that you do not need to either.

To work on a problem like this, you need to familiarize yourself with all the steps involved (we call this "problem solving") by breaking them down and dealing with them one at a time. How many times, while working on this, have you written A SHORT, SEPARATE PROGRAM to check your understanding of the commands and concepts involved? If the answer is none, your attitude or methodology MUST change in time. So how about now? This is the natural form of computer programming anyway.

Most likely no one cares about or is interested in your project. However, there is a chance someone will take an interest in a problem, if you present it properly.

Best of all, almost certainly someone can answer a specific question ("is this the correct use of ???), but you don't have one yet. If you can write a short (25 lines or less) piece of code that is A COMPLETE, SELF-CONTAINED PROGRAM and explain what you wanted each significant block to accomplish, I promise I will solve your problem. If you don't do it first, that is.

I know it seems a hassle at first, like you are wasting time. But eventually you will recognize where time really gets wasted, and where it does not. Plus your coding (as opposed to pondering and hand-wringing) skills will naturally improve with every

Code:

int main () {

you start.

I wrote a code that can find the largest out of 5 numbers entered but i not exactly sure where to go from here to be able to get the 3 largest numbers of the 5 to print out. I just need a little guidance on where to go from here and I should be able to figure out the rest. Thanks

Code:

#include<stdio.h>

int main(void)

{
int n1, n2, n3, n4, n5;

printf("Enter five integer numbers\n");
scanf("%d,%d,%d,%d,%d",&n1,&n2,&n3,&n4,&n5);

printf("The largest of the five integers is ");

if (n1>n2 && n1>n3 && n1>n4 && n1>n5) 
printf("%d",n1);
else{ if (n2>n1 && n2>n3 && n2>n4 && n2>n5)
printf("%d", n2);
else if (n3>n1 && n3>n2 && n3>n4 && n3>n5)
printf("%d", n3);
else if (n4>n1 && n4>n2 && n4>n3 && n4>n5)
printf("%d", n4);
else if (n5>n1 && n5>n2 && n5>n3 && n5>n4)
printf("%d", n5);}

return(0);

}

The secret purpose of functions is to streamline stuff like this. They also provide all kinds of opportunities of their own. Here's my idea:

Code:

#include<stdio.h>

/* use an array so we can apply a loop */
int n[5];

	/* a function to find the highest number and replace it */
int sortray () { 
	int high=n[0],low=n[0],i,t=0,r;    /* "t" is a tag */
	for (i=1; i<5; i++) {
		if (n[i]>high) { high=n[i]; t=i; }
		if (n[i]<low) { low=n[i]; }
	}
	r=n[t];	/* store the high value */
		/* now replace the high value */
	n[t]=low;
	return r;
}


int main() {
	int i; 
		
	printf("Enter five integer numbers\n");
	scanf("%d,%d,%d,%d,%d",&n[0],&n[1],&n[2],&n[3],&n[4]);

	/* use the function 3 times! */
	for (i=0; i<3; i++) printf("%d\n",sortray());

        return(0);

}

I am pretty sure you cannot "cheat" this, but I am not very good with math. Or perhaps it's more of a logic question, in which case I would say with authority you cannot cheat this

Code:

Enter five integer numbers
5,7,9,131,-99
131
9
7

Notice that n is now a global variable.

Thanks for your help with the code.

I hope that you do understand what the code is doing.. use that as your reference for learning..

Another approach, more efficient on larger data sets: sort the array and print the last three elements.

In C, you already have qsort() for arrays, so there's essentially no additional work left.

Greets,
Philip

Originally Posted by Snafuist

Another approach, more efficient on larger data sets: sort the array and print the last three elements.

Good suggestion, though sorting is not necessary to find the largest n elements as they can be found in linear time on average. Unfortunately, the C standard library has no equivalent of the C++ standard library's std::nth_element().

Originally Posted by laserlight

Good suggestion, though sorting is not necessary to find the largest n elements as they can be found in linear time on average.

For constant n << sizeof(our_array), this holds true. Simply iterate over the array elements and keep track of the largest, second-largest and so on. Let X denote the size of the array, then the asymptotic runtime is O(X + n*log(X)), which is linear for n<<X.

(Quiz question: proof that O(X + n*log(X)) is indeed the correct asymptotic runtime)


However, in the general case, i.e. on average, this is wrong.

Proof by contradiction:

Fact 1: The lower bound for sorting is O(X*log(X)).
Fact 2: The algorithm described above finds the first n largest elements in a sorted manner in linear time and this is optimal (I have to look at each of the array elements at least once).

Now suppose I could find the n largest elements of an array in linear time (on average) in a sorted manner. Then I could especially find all of them in linear time (on average) in a sorted manner.
=> Contradiction to the sorting lower bound.

Unfortunately, the C standard library has no equivalent of the C++ standard library's std::nth_element().

But it would be very easy to implement. And again, for n<<X, linearity holds true. But nth_element() has a runtime of O(n), so finding e.g. all X largest elements yields runtime O(X*X).


In general, as soon as I can express n in terms of X, e.g. n = X/1000, the runtime is not linear. Thus, the runtime is not linear for almost all values of n.


For practical purposes, reasonably sized arrays and constant n, it is indeed linear sometimes. It's just that I'm generally more interested in complexity theory than in programming. I know I sometimes sound a bit offensive, but this is mostly due to my poor English. My post is not meant to be an offense, I'm just enjoying a free afternoon :-)

Greets,
Philip

Originally Posted by Snafuist

Fact 1: The lower bound for sorting is O(X*log(X)).

As I noted, you do not need to sort, so quoting the lower bound of comparison based sorting is irrelevant.

Originally Posted by Snafuist

Now suppose I could find the n largest elements of an array in linear time (on average) in a sorted manner.

That is not correct. The aim is to find the n largest elements, not to find the n largest elements in sorted order (in which case a partial sort might be more appropriate, but I suppose you could find the n largest elements and then sort that subrange only).

The idea is to partition the array as in quick sort. If after the partitioning, it turns out that the pivot element is in the nth position, then you know that all the elements in one partition are the n largest elements. If not, you can determine in which partition the n largest elements must be in, and thus pick another pivot in that partition, and repeat the process recursively. This algorithm can perform as bad as quick sort (quadratic time complexity in the worst case), but on average it has linear asymptotic running time.

Originally Posted by Snafuist

But nth_element() has a runtime of O(n), so finding e.g. all X largest elements yields runtime O(X*X).

No, nth_element partitions the range such that all the elements "less than" the nth element are in one partition, and all the elements "not less than" the nth element are in the other partition. It does this partitioning in linear time on average.

Aah, having read the original post once again, I noticed that I implicitly made the assumption that the output should be like:

Largest element: ...
2nd-largest: ...
3rd-largest: ...

My proof is not wrong, but if order doesn't matter, you are of course right in that there's a faster way to do it.


The same applies for your second quote about std::nth_element(). Didn't think about partitioning, because I tried to keep the sortedness property.


I promise that from now on I'll read posts twice. ;-)

Greets,
Philip

Originally Posted by Snafuist

My proof is not wrong, but if order doesn't matter, you are of course right in that there's a faster way to do it.

I suspect that even if order matters, using nth element partitioning followed by a sort on the desired range would be faster than sorting the entire array and then picking the desired range. The reason is that the sort is only performed on the reduced range, and it is the sort's complexity that dominates the overall complexity, so it could be a substantial advantage if you only want say, the top 10% of the array.