finding largest numbers

[ramu]

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

 

[phus.lu]

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

 

[Richard Heathfield]

(e-mail address removed) said:

qsort & bsearch<stdlib.h> perhaps better.

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

 

[Richard Heathfield]

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.

 

[Keith Thompson]

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.

 

[Morris Dovey]

ramu (in (e-mail address removed)) 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.

 

[Richard G. Riley]

(e-mail address removed) said:



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

 

[Thad Smith]

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.

 

[Richard Heathfield]

Richard G. Riley said:

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');

 

[Frederick Gotham]

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 );
}

 

[Richard Tobin]

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

 

[Christopher Benson-Manica]

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.

 

[Dann Corbit]

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

 

[Keith Thompson]

(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 };

 

[Frederick Gotham]

Keith Thompson posted:

(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
compile-time constant if it is initialised with a compile-time 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 well-defined, so I
don't see a problem.


Also, as I've said before, I avoid macros wherever possible.

 

[Morris Dovey]

Christopher Benson-Manica (in [email protected]) said:

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

Tsk-tsk. I'm not even remotely encouraging the OP to re-order
anything - only to compare values and copy when appropriate...

Do you have a solution that doesn't compare _any_ values? :-D

 

[Keith Thompson]

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 well-defined, 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.

 

[$hiv.....]

#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 < num && num < max[i-1] )
max = num;

}
Start_reading_the_file_once_again();
}

print_number_from max[1] to max[5];

 

[Christopher Benson-Manica]

Do you have a solution that doesn't compare _any_ values? :-D

It's unfortunate that bogo-sort is technically a sorting algorithm

(Point taken!)

 

[Dann Corbit]

/*
** 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 0-07-013143-0
*/


/*
** 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;
A = 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 >= x));
if (i < j) {
temp = A;
A = A[j];
A[j] = temp;
} else
return j;
}
}