473,888 Members | 1,522 Online

finding largest numbers

Hi,
I have, suppose 1000 numbers, in a file. I have to find out 5
largest numbers among them without sorting. Can you please give me an
efficient idea to do this? My idea is to put those numbers into a
binary tree and to find the largest numbers. How else can we do it?

Regards

Jun 26 '06 #1
19 8602
qsort & bsearch<stdlib. h> perhaps better.
ramu wrote:
Hi,
I have, suppose 1000 numbers, in a file. I have to find out 5
largest numbers among them without sorting. Can you please give me an
efficient idea to do this? My idea is to put those numbers into a
binary tree and to find the largest numbers. How else can we do it?

Regards

Jun 26 '06 #2
ph*****@gmail.c om said:
ramu wrote:
Hi,
I have, suppose 1000 numbers, in a file. I have to find out 5
largest numbers among them without sorting. Can you please give me an
efficient idea to do this? My idea is to put those numbers into a
binary tree and to find the largest numbers. How else can we do it?
qsort & bsearch<stdlib. h> perhaps better.

Which syllable of "without sorting" were you struggling with?

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Jun 26 '06 #3
ramu said:
Hi,
I have, suppose 1000 numbers, in a file. I have to find out 5
largest numbers among them without sorting. Can you please give me an
efficient idea to do this? My idea is to put those numbers into a
binary tree and to find the largest numbers. How else can we do it?

A binary tree would basically be a sorting technique, which you say you're
not allowed to do.

Just set up an array m of five numbers, and set them all to INT_MIN.

Then do something like this:

count = 0;
while(successfu lly_got_next_nu mber_in_file_in to_n)
{
++count;
c = 0;
for(j = 0; c == 0 && j < 5; j++)
{
if(n > m[j])
{
m[j] = n;
c = 1;
}
}
}
if(count < 5)
{
you will still have some INT_MIN entries in n, which you should disregard
when reporting the results of the program.
}

If you are allowed to keep m sorted, there is a way to reduce the number of
comparisons still further, but my answer assumes you are not allowed to do
any sorting at all.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Jun 26 '06 #4
ph*****@gmail.c om writes:
ramu wrote:
I have, suppose 1000 numbers, in a file. I have to find out 5
largest numbers among them without sorting. Can you please give me an
efficient idea to do this? My idea is to put those numbers into a
binary tree and to find the largest numbers. How else can we do it?

qsort & bsearch<stdlib. h> perhaps better.

Pleaes don't top-post. I've corrected it here.
See <http://www.caliburn.nl/topposting.html >.

Since the original question said "without sorting", I don't think
qsort() is going to be part of any solution.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Jun 26 '06 #5
ramu (in 11************* *********@p79g2 00...legr oups.com) said:

| I have, suppose 1000 numbers, in a file. I have to find out 5
| largest numbers among them without sorting. Can you please give me
| an efficient idea to do this? My idea is to put those numbers into a
| binary tree and to find the largest numbers. How else can we do it?

Initialize five variables (or five elements of an array) to a value
less than or equal to the smallest possible number in the file.

Make a single pass through the file, counting the numbers you're
checking, and if any number is larger than the smallest number of the
five, replace the smaller number with the larger number you found in
the file.

At the end of the file, make sure that you counted to at least five.
Your five values should be the five largest values from the file.

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto
Jun 26 '06 #6
ramu wrote:
I have, suppose 1000 numbers, in a file. I have to find out 5
largest numbers among them without sorting. Can you please give me an
efficient idea to do this?

Starting with the first 5 numbers, enter them into a heap with the
smallest value at the root. Scan through the array. If the entry is
larger than the heap root, replace the root with the entry, then
re-heapify. When you are finished scanning, the heap contains the 5
largest values. A heap is partially ordered, so you are never fully
sorting either all entries or the heap.

--
Jun 26 '06 #7
Richard Heathfield <in*****@invali d.invalid> writes:
ph*****@gmail.c om said:
ramu wrote:
Hi,
I have, suppose 1000 numbers, in a file. I have to find out 5
largest numbers among them without sorting. Can you please give me an
efficient idea to do this? My idea is to put those numbers into a
binary tree and to find the largest numbers. How else can we do it?

qsort & bsearch<stdlib. h> perhaps better.

Which syllable of "without sorting" were you struggling with?

With a name like "phus.lu" probably most of them I would have
thought. Otherwise I would guess the "out" syllable bit when combined
with the syllable "with" to form the word "without". Since the OP
obviously didnt even understand what "without sorting" meant and
proposed a binary tree then its not so out of the question to suggest
qsort too. Or?

And, I might suggest, the poster was suggesting that qsort was better
than using a binary tree. And hes right...
Jun 26 '06 #8
Richard G. Riley said:

<snip>

And, I might suggest, the poster was suggesting that qsort was better
than using a binary tree. And hes right...

Well, bear in mind that the data is coming in from file, and there might not
be sufficient RAM to store all the numbers contiguously. Bye-bye array.

Of course, there might not be sufficient RAM to store all the numbers, full
stop. Bye bye binary tree.

On reflection, the method I suggested is borken too. One has no option but
to at least keep /that/ part sorted.

So it will be something like:

int m[] = { INT_MIN, INT_MIN, INT_MIN, INT_MIN, INT_MIN, INT_MIN };
int j;
unsigned long count = 0;

while(you manage to retrieve n from the file)
{
++count;
for(j = 5; j > 0; j--)
{
if(n > m[j - 1])
{
m[j] = m[j - 1];
m[j - 1] = n;
}
else
{
j = 0;
}
}
}

if(count > 5) count = 5;

printf("In ascending order:\n");
while(count--)
{
printf(" %d", m[count]);
}
putchar('\n');

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Jun 26 '06 #9
ramu posted:
Hi,
I have, suppose 1000 numbers, in a file. I have to find out 5
largest numbers among them without sorting. Can you please give me an
efficient idea to do this? My idea is to put those numbers into a
binary tree and to find the largest numbers. How else can we do it?

Regards

Maybe something like:
(Unchecked code, likely to contain a thousand little errors)
#include <string.h>
int global_array[1000];
/* Lets pretend they have random (but legitimate) values */
unsigned const magic = 5;
typedef struct IntsArray {
int array[magic];
} IntsArray;
void ShiftDown( int * const p,
unsigned const quantity,
unsigned const places )
{
int * const q = p + places;

memmove( p, q, quantity );
}

IntsArray GetTopX( const int *p, const int * const p_over )
{
IntsArray fi = {};

int *pi =
fi.array + (sizeof(fi.arra y) / sizeof(*fi.arra y) - 1);

do
{
for( unsigned i = 0; i != magic; ++i, --pi )
{
if ( *p > *pi )
{
ShiftDown( fi.array, 5 - i, 5 - i );
/* Probably an error on the above line */
}
}
} while (p != p_over);
}
int main()
{
IntsArray ia = GetTopX( global_array, global_array + 1000 );
}

--

Frederick Gotham
Jun 26 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.