Search code examples
javaarraylistselection-sort

Selection sort with arraylists?


I have to adapt selection sort for a school thing. The purpose is to return ranking of players with winners coming first, etc. Equally ranked players should be listed in the same order as they occur in the tournament list.

public ArrayList<Player> ranking() {
    ArrayList<Player> result = new ArrayList<Player>();
    // Supply this code!
    return result;

Now heres my attempt at adapting selection sort

    int smallInt = 0;
    int j=0;
    int smallIntIndex = 0;      

    for(int i=1;i<players.size();i++){
        smallInt = result.get(i-1).totalScore();
        smallIntIndex = i-1;
        for(j=i;j<players.size();j++){
            if(result.get(j).totalScore()<smallInt){
                smallInt = result.get(j).totalScore();
                smallIntIndex = j;                    
            }
        }
        int temp = result.get(smallIntIndex).totalScore();
        result.set(smallIntIndex, result.get(i-1));
        result.set(i-1, temp);
    }
    return result;

And the only line that gives me error is the very last

result.set(i-1, temp); //The method set(int, Player) in the type 
                       //ArrayList<Player> is not applicable for the arguments (int, int)

Any idea what I'm doing wrong? Is most of the adaptation correct? ANY HELP APPRECIATED. Thanks

p.s. please don't suggest comparators or stuff like that, that's not what I'm looking for.


Solution

  • A couple of things:

    • you are initializing an empty result array, but the algorithm works on existing arrays by swapping elements. You must initialize result with the values of players

      List<Player> result = new ArrayList<Player>(players);
      
    • variable temp must be of type Player instead of int

      Player temp = result.get(smallIntIndex);
      
    • the outer loop must start from index 0, not 1

    • the outer loop must end at players.size() - 1
    • the inner loop must start from index i+1
    • you swap elements every time in the outer loop, this is not correct. Only swap them when a new minimum is found

    The corrected code:

    public ArrayList<Player> ranking() {
        List<Player> result = new ArrayList<Player>(players);
        int smallInt = 0;
        int j=0;
        int smallIntIndex = 0;      
    
        for(int i=0;i<result.size() - 1;i++){
            smallInt = result.get(i).totalScore();
            smallIntIndex = i;
            for(j=i+1;j<result.size();j++){
                if(result.get(j).totalScore()<smallInt){
                    smallInt = result.get(j).totalScore();
                    smallIntIndex = j;                    
                }
            }
    
            if (i != smallIntIndex) {
                Player temp = result.get(smallIntIndex);
                result.set(smallIntIndex, result.get(i));
                result.set(i, temp);
            }
        }
        return result;
    }
    

    EDIT: You ask that the sorted results must go into a separate results array, which is initially empty. Here's a way to do it:

    public ArrayList<Player> ranking() {
        List<Player> result = new ArrayList<Player>();
        int smallInt = 0;
        int j=0;
        int smallIntIndex = 0;      
    
        for(int i=0;i<players.size() - 1;i++){
            smallInt = players.get(i).totalScore();
            smallIntIndex = i;
            for(j=i+1;j<players.size();j++){
                if(players.get(j).totalScore()<smallInt){
                    smallInt = players.get(j).totalScore();
                    smallIntIndex = j;                    
                }
            }
    
            if (i != smallIntIndex) {
                Player player = players.get(smallIntIndex);
    
                result.add(player);
                players.set(smallIntIndex, players.get(i));
            }
        }
        return result;
    }
    

    Reference: Wikipedia's article on selection sort