Java Help - sorting an array, but not the usual way

Author

sorting an array, but not the usual way

jctown@nb.sympatico.ca

2006-08-13, 8:02 am

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,

Patricia Shanahan

2006-08-13, 8:02 am

jctown@nb.sympatico.ca wrote:
> 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?

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

vir calimlim

2006-08-14, 8:01 am

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

vir

Dale King

2006-08-29, 10:01 pm

Patricia Shanahan wrote:
> jctown@nb.sympatico.ca wrote:
>
> 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

--
Dale King

Sponsored Links