[Tutor] Any ideas on designing an efficient algorithm for this problem?

[Alan Gauld]

On 24/06/2023 10:28, marc nicole wrote:
> I want to get the 100th greatest number in an array of one billion
> elements. How to do that efficiently? I was thinking of dividing the
> original array into smaller arrays and then get the biggest number in each
> of them and then compare with others etc... But any better ideas here?

I suspect the most efficient is probably using the
builtin max() function, unless... You get into threading
or another concurrency mechanism.

In that case splitting your list into N chunks
and assigning the max() to different threads and
then bringing the N, results together into a
single call to max might be faster.

But on my M1 Mac it took less than 90 seconds for a billion
item list using vanilla max(). If 90s is too long then by
all means try concurrency.

-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos