473,888 Members | 1,522 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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.

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

Similar topics

12
3418
by: e271828 | last post by:
Hi, I'm helping to work a developer tool that verifies a given HTML element has a given attribute (e.g., that all LABEL elements have a FOR attribute, all INPUT elements have an ID attribute, etc.). Pretty much all of the functionality is working except a feature that shows in which line of the HTML source a violation of the user-set rule occurs (e.g., where a LABEL element doesn't have a FOR attribute). There doesn't seem to be a...
25
4381
by: Subra | last post by:
Hi, What is the best way to find the 1000 largest numbers from the file having hell lot of entries ? Can you please help me to find out the way ? Do I need to go for B+ trees ?? Please help, Subramanya M
5
1890
by: Ramdas | last post by:
I am doing some HTML scrapping for a side project. I need a method using sgmllib or HTMLParser to parse an HTML file and get line nos of all the tags I tried a few things, but I am just not able to work with either if the parsers.
3
29169
by: Bouzy | last post by:
I have a list of words and am trying to replace all the numbers in my list with whitespace. for word in words: numbers = re.search('+', word) word = clearup(word) if word in dictionary: pass else: print word
0
9961
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9800
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
1
10885
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10439
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
9597
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
7148
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
1
4642
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4244
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3252
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.