Hello, I'm having some problems returning the 3 largest values from an array.

Basically, I've got a value1, value2 and value3, which need to be the 3 largest values from an array. A friend and I have literally tried for hours to make a working method to create this, resulting in things like this (we're getting the values from a HashMap and put it in an array):
setStrings = randomHashMap.keySet();
String[] tempArray = (String[])setStrings.toArray(new String[20]);
String tempString = tempArray[index];
Integer test = (Integer)randomHashMap.get(tempString);
int a = test.intValue();

for(int index=0; index Set setStrings1 = randomHashMap.keySet();
String[] tempArray1 = (String[])setStrings1.toArray(new String[20]);
String tempString1 = tempArray1[index1];
Integer test1 = (Integer)randomHashMap.get(tempString1);
int b = test1.intValue();
if(a >= B){
if(a>value1){
if(value1>value2){
value2=value1;
}
else{
value3=value1;
}
value1 = a;
if(b>value2) {
if(value2>value3){
value2 = b;
}
else{
value3=value2;
value2 = b;
}
}
else{
if(value1>value2){
value2=value1;
}
else{
value3=value1;

}
value1=b;
}


Now I know the above method doesn't work. I've tried dozens of variants on this type of solution (also making a second loop, but I thought it should be possible to get the highest values from a list using only 1 value from the list).
Can anybody help? Me and my buddy are getting very tired and our solutions aren't becoming better.
Any help would be very appreciated!

Are you just trying to sort the 3 elements into highest to low?

You're making things more complex than they need to be if so. Just use a bubble sort, which I will give an example of below.

//assuming the presence of an int array with some values filled inint n = array.length;int pass = 0;for(pass = 1; pass < n ; pass++){     for(int i = 0; i < n-pass ; i++){           if(array[i] < array[i+1]);    //finish code to switch yourself      }}

Assumption: You have a container of n items and want to take the largest 3. (That is what I understood from the question).

Note: If you find yourself using numbered variables, you need to use some sort of container (an array probably).

The simplest way is to put the integers into a ordered container (hint: an array). Sort using Arrays.sort and take the last three values (which will be the largest). This is theoretically slower than the most effective algorithm but is neatest code wise.

Another way, possibly faster for large arrays but much more confusing (I don't have a clue if I got this correct):

//So lets say we have a array that holds the highest items (rather than using value1, value2 et al)int highest[] = new int[3];//So now we look through the container (HashMap/whatever)for ( int value : container ){    //So now we look down the list of highest values    //trying to find where value slots into it. the highest    //array is ordered highest first (at index 0)    for ( int i = 0; i < highest.length; i++ ){        //if the value is greater than the ith value of highest, we        //shift the other ith value and above up one to slot the        //new value in.        if ( value > highest[i] ){            for ( int j = i; j < highest.length - 1; i++ ){                hightest[j + 1] = highest[j];            }            hightest[i] = value;            break;        }    }}

Let me point out. If it isn't time critical, just sort it and take the top 3 items. Much simpler code wise.

import java.util.Arrays;

Arrays.sort(nameofarray);

Edit: stupid semicolons

Bah, that's the easy way out

Always handy to learn how to write your own sorting algorithm.

Yacoby: that code looks like it could be more efficient in theory but it also looks monstrous (no offence ).

Agreed on principle, but in reality I'll never do work done for me

But since you're working in java, it's fair to assume that any work done for you by the language itself is probably awful. Kind of like the entire language.

Ouch

Though, in all honesty, if not for having done stuff with arrays recently in java (during which time I learned about Arrays.sort), I'd have probably done a bubble sort too. May not be fast, but it's simple.

Non taken. I hope I pointed that it is terrible in my post. It is also 2AM which is not helping my coding ability. If I used a list the code would be much more understandable as I could insert into it. But then I would have to remember an API.

Of which bubble sort is a terrible terrible example. Insertion Sort is a more natural way of looking at a sort but you are going to write a decent algorithm for a very large list where you don't know its state implement timsort (a mergesort derivative). Basically what JDK7 uses.

That's true, I just suggested bubble sort as it's generally the first sort taught to beginners (at least that's what I was taught first) and the OP seems to be just starting out. I would of course use something a lot better in my own code, but I find that the concept of bubble sort pretty easy to understand.

edit: Personally I favour Quicksort if I can use it, but I've been working on expanding my knowledge of sorting algorithms, one of the little side hobbies of mine when it comes to code. That and fractals, I love me some fractals.

Timsort is a pain in the ass to implement, though. If you really need to quickly implement an efficient sorting algorithm, combsort11 is the best choice. It's a relatively simple improvement of bubblesort, but very fast in practice even on large containers and with the average complexity of O(n*log(n)).

Quicksort has the issue of pivot choice, which if the wrong one is selected every time is running time is O(n²). Merge sort doesn't have this issue which is why it is used in many standard libraries.


My comment was that if you were going to write something decent, that is what you would probably implement.

However IMHO you shouldn't really be implementing common algorithms unless you have a problem with the standard implementation. :shrug:

Thanks for all the suggestions! And sorry for the unclear language..

I eventually managed to ( a couple of hours back) to write a correct sorting algorithm (10 if's!) but if array has its own sorting algorithm I will gladly use that one. Thanks a lot!

Sorry for the bump, but I got another question.


I need to get a key from a HashMap. The key has a unique value and vice versa, leading me to believe there must be a better way to store this key so I can easily retrieve it. However I'm only allowed to use standard classes contained in Java (everything on this list : http://download.oracle.com/javase/6/docs/api/index.html)

Does anybody have a good suggestion for another tool to use, or to get a key out of the HashMap that belongs to a specific value?
Note, that I can't switch the value and key positions due to the method.

You probably want to use a Bimap, not a HashMap, however as a quick and easy solution you can just iterate through a HashMap. It is however O(n) (Read: Horribly slow for large maps)

for (Map.Entry entry : map.entrySet()) {    if ( entry.getValue() == "MyVal" ){        return entry.getKey();    }}

The other way would be to maintain two HashMaps, one mapping Key->Val and the other Val->Key