P: n/a

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  
Share this Question
P: n/a

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  
P: n/a
 ph*****@gmail.com 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)  
P: n/a

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(successfully_got_next_number_in_file_into_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)  
P: n/a
 ph*****@gmail.com 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 toppost. 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_Keith) 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.  
P: n/a

ramu (in 11**********************@p79g2000cwp.googlegroups. 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  
P: n/a

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
reheapify. 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.

Thad  
P: n/a

Richard Heathfield <in*****@invalid.invalid> writes: ph*****@gmail.com 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...  
P: n/a

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. Byebye 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)  
P: n/a

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.array) / sizeof(*fi.array)  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  
P: n/a

In article <11**********************@p79g2000cwp.googlegroups .com>,
ramu <ra******@gmail.com> 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?
Find the largest number. Find the next largest number. Etc.
This will take about 5n comparisons. Obviously it requires at least
n comparisons. How efficient do you need?
 Richard  
P: n/a

Morris Dovey <mr*****@iedu.com> wrote: 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.
Determining which number of the five is smallest necessarily involves
an operation resembling sorting, which the OP was explicitly forbidden
to use.

Christopher BensonManica  I *should* know what I'm talking about  if I
ataru(at)cyberspace.org  don't, I need to know. Flames welcome.  
P: n/a

"ramu" <ra******@gmail.com> wrote in message
news:11**********************@p79g2000cwp.googlegr oups.com... 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?
Your question is better suited to news:comp.programming.
The answer to your question is called Quickselect() and is described in
detail in
T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to
Algorithms, Cambridge: The MIT Press, 1990.  
P: n/a

Frederick Gotham <fg*******@SPAM.com> writes:
[...] (Unchecked code, likely to contain a thousand little errors)
[...] unsigned const magic = 5;
typedef struct IntsArray { int array[magic]; } IntsArray;
The "array" member is a variable length array, so this won't work in
C90. (I'm not certain that a VLA is allowed as a struct member even
in C99.)
Counterintuitively, "magic", even though it's declared const, is not a
constant expression.
You can avoid this either by declaring magic as a macro (preferably MAGIC):
#define MAGIC 5
or, if you don't mind abusing enumerated types, as an enumeration constant:
enum { MAGIC = 5 };

Keith Thompson (The_Other_Keith) 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.  
P: n/a

Keith Thompson posted: Frederick Gotham <fg*******@SPAM.com> writes: [...] (Unchecked code, likely to contain a thousand little errors) [...] unsigned const magic = 5;
typedef struct IntsArray { int array[magic]; } IntsArray;
The "array" member is a variable length array, so this won't work in C90. (I'm not certain that a VLA is allowed as a struct member even in C99.)
Counterintuitively, "magic", even though it's declared const, is not a constant expression.
C++ habits getting the better of me. (A const object in C++ can act as a
compiletime constant if it is initialised with a compiletime constant).
You can avoid this either by declaring magic as a macro (preferably MAGIC): #define MAGIC 5 or, if you don't mind abusing enumerated types, as an enumeration constant: enum { MAGIC = 5 };
It seems that there's variety in opinion when it comes to using enum's
for constants. Some, like yourself, seem to view it as abuse, but I like
to think that it's just making use of all the functionality we're given
in the language.
The results of using an enum for constants is welldefined, so I
don't see a problem.
Also, as I've said before, I avoid macros wherever possible.

Frederick Gotham  
P: n/a

Frederick Gotham <fg*******@SPAM.com> writes: Keith Thompson posted:
[...] You can avoid this either by declaring magic as a macro (preferably MAGIC): #define MAGIC 5 or, if you don't mind abusing enumerated types, as an enumeration constant: enum { MAGIC = 5 };
It seems that there's variety in opinion when it comes to using enum's for constants. Some, like yourself, seem to view it as abuse, but I like to think that it's just making use of all the functionality we're given in the language.
My use of the term "abuse" is half jocular. It's an abuse in the
sense that it's not consistent with the originally intended use of the
construct. I actually think it's a *good* abuse.
The results of using an enum for constants is welldefined, so I don't see a problem.
Nor do I (except that it's limited to type int.
Also, as I've said before, I avoid macros wherever possible.
I merely avoid them whenever practical.

Keith Thompson (The_Other_Keith) 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.  
P: n/a

Christopher BensonManica (in e7**********@chessie.cirr.com) said:
 Morris Dovey <mr*****@iedu.com> wrote:

 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.

 Determining which number of the five is smallest necessarily
 involves an operation resembling sorting, which the OP was
 explicitly forbidden to use.
Tsktsk. I'm not even remotely encouraging the OP to reorder
anything  only to compare values and copy when appropriate...
Do you have a solution that doesn't compare _any_ values? :D

Morris Dovey
DeSoto Solar
DeSoto, Iowa USA http://www.iedu.com/DeSoto  
P: n/a

#define NUM_OF_BIGGEST 5
int i,j,num,max[NUM_OF_BIGGEST+1]; /*if u want only 5 biggest
numbers*/
max[0] = 0xffff;
for( i = 1;i <= NUM_OF_BIGGEST; i++)
for( j = 1;j <= 1000; j++)
{
get_next_num(&num);
if(max[i] < num && num < max[i1] )
max[i] = num;
}
Start_reading_the_file_once_again();
}
print_number_from max[1] to max[5];  
P: n/a

Morris Dovey <mr*****@iedu.com> wrote: Do you have a solution that doesn't compare _any_ values? :D
It's unfortunate that bogosort is technically a sorting algorithm :)
(Point taken!)

Christopher BensonManica  I *should* know what I'm talking about  if I
ataru(at)cyberspace.org  don't, I need to know. Flames welcome.  
P: n/a

/*
** This solves the general case for the selection problem in average case
** linear time.
** D. Corbit.
** This code is explicitly granted to the public domain.
*/
#include <stdlib.h>
typedef double Etype;
extern Etype RandomSelect(Etype * A, size_t p, size_t r, size_t i);
extern size_t RandRange(size_t a, size_t b);
extern size_t RandomPartition(Etype * A, size_t p, size_t r);
extern size_t Partition(Etype * A, size_t p, size_t r);
/*
**
** In the following code, every reference to CLR means:
**
** "Introduction to Algorithms"
** By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
** ISBN 0070131430
*/
/*
** CLR, page 187
*/
Etype RandomSelect(Etype A[], size_t p, size_t r, size_t i)
{
size_t q,
k;
if (p == r)
return A[p];
q = RandomPartition(A, p, r);
k = q  p + 1;
if (i <= k)
return RandomSelect(A, p, q, i);
else
return RandomSelect(A, q + 1, r, i  k);
}
size_t RandRange(size_t a, size_t b)
{
size_t c = (size_t) ((double) rand() / ((double) RAND_MAX + 1)
* (b  a));
return c + a;
}
/*
** CLR, page 162
*/
size_t RandomPartition(Etype A[], size_t p, size_t r)
{
size_t i = RandRange(p, r);
Etype Temp;
Temp = A[p];
A[p] = A[i];
A[i] = Temp;
return Partition(A, p, r);
}
/*
** CLR, page 154
*/
size_t Partition(Etype A[], size_t p, size_t r)
{
Etype x,
temp;
size_t i,
j;
x = A[p];
i = p  1;
j = r + 1;
for (;;) {
do {
j;
} while (!(A[j] <= x));
do {
i++;
} while (!(A[i] >= x));
if (i < j) {
temp = A[i];
A[i] = A[j];
A[j] = temp;
} else
return j;
}
}   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 8127
 replies: 19
 date asked: Jun 26 '06
