sorting an array, but not the usual way

Thread view:

jctown@nb.sympatico.ca - 13 Aug 2006 12:18 GMT

I have an array of 49 integers. Each bucket contains a count of the
number of times that number (the index of the array) was picked when I
asked for 6 numbers between 1 and 49 1,000,000 times.

What I need to do is create a new array, this time with only 6 integers
where they contain the top 6 picks.

So, if my bigList contains

1) 123122
2) 233422
.
.
.
49) 231221

The final array would have say
2, 7, 29, 40, 12, 49 if those 6 numbers were picked the most.
I need an algorithm....Array.sort messes up the array so I can't tell
when numbers were picked the most. Any ideas?

PS - This is not a homework assignment, I am just trying to do some
elementary Java programming on my own to put into practice what I have
been learning,

Reply to this Message

Patricia Shanahan - 13 Aug 2006 12:41 GMT

> I have an array of 49 integers. Each bucket contains a count of the
> number of times that number (the index of the array) was picked when I
[quoted text clipped - 16 lines]
> I need an algorithm....Array.sort messes up the array so I can't tell
> when numbers were picked the most. Any ideas?

Essentially, you are doing "k largest elements", and sort is one means
to that end.

Here are a couple of approaches:

1. Find the six largest elements without sorting. Do a single scan of
the array, keeping track of the value and index for each of the 6
largest elements found so far. Store the index values for the final
version of the 6 largest in the new array.

As a variant, keep track of only the values of the six largest elements,
and do a final scan to find them and write their index values to a new
array.

2. Create a new array containing objects with both the value and index
for each entry in the original array. Sort on value, pick the last six
elements, and store their index values in the new array.

> PS - This is not a homework assignment, I am just trying to do some
> elementary Java programming on my own to put into practice what I have
> been learning,

Reply to this Message

Dale King - 29 Aug 2006 20:44 GMT

>> I have an array of 49 integers. Each bucket contains a count of the
>> number of times that number (the index of the array) was picked when I
[quoted text clipped - 19 lines]
> Essentially, you are doing "k largest elements", and sort is one means
> to that end.

For a thorough discussion of alternatives for selection see this
Wikipedia article:

http://en.wikipedia.org/wiki/Selection_algorithm

Signature

Dale King

Reply to this Message

vir calimlim - 14 Aug 2006 11:36 GMT

if you don't want to write your own sort logic, try class SortedSet

vir

Reply to this Message

sorting an array, but not the usual way

Free Magazines