C - finding largest numbers

Author

finding largest numbers

ramu

2006-06-26, 3:57 am

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@gmail.com

2006-06-26, 3:57 am

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

Richard Heathfield

2006-06-26, 3:57 am

phus.lu@gmail.com said:

> ramu wrote:
[color=darkred]
> 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)

Richard Heathfield

2006-06-26, 3:57 am

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_fi
le_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)

Keith Thompson

2006-06-26, 7:56 am

phus.lu@gmail.com writes:
> ramu wrote:
>
> 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_Keith) kst-u@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.

Morris Dovey

2006-06-26, 7:56 am

ramu (in 1151305606.923958.208980@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

Thad Smith

2006-06-26, 7:56 am

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.

--
Thad

Richard G. Riley

2006-06-26, 7:56 am

Richard Heathfield <invalid@invalid.invalid> writes:

> phus.lu@gmail.com 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...

Richard Heathfield

2006-06-26, 7:56 am

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)

Frederick Gotham

2006-06-26, 6:56 pm

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

Christopher Benson-Manica

2006-06-26, 6:56 pm

Morris Dovey <mrdovey@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 Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.

Dann Corbit

2006-06-26, 6:56 pm

"ramu" <ramu.ask@gmail.com> wrote in message
news:1151305606.923958.208980@p79g2000cwp.googlegroups.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.

Keith Thompson

2006-06-26, 6:56 pm

Frederick Gotham <fgothamNO@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) kst-u@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.

Frederick Gotham

2006-06-26, 6:57 pm

Keith Thompson posted:

> Frederick Gotham <fgothamNO@SPAM.com> writes:
> [...]
> [...]
>
> 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.

--

Frederick Gotham

Keith Thompson

2006-06-26, 6:57 pm

Frederick Gotham <fgothamNO@SPAM.com> writes:
> Keith Thompson posted:
[...]
>
> 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.

--
Keith Thompson (The_Other_Keith) kst-u@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.

Morris Dovey

2006-06-26, 6:57 pm

Christopher Benson-Manica (in e7p57h$88e$1@chessie.cirr.com) said:

| Morris Dovey <mrdovey@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.

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

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto

$hiv.....

2006-06-27, 7:56 am

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

}
Start_reading_the_file_once_again();
}

print_number_from max[1] to max[5];

Christopher Benson-Manica

2006-06-27, 7:56 am

Morris Dovey <mrdovey@iedu.com> wrote:

> 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!)

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.

Dann Corbit

2006-06-27, 6:56 pm

/*
** 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[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;
}
}

Sponsored Links