How to insertion sort an ArrayList of Strings alphabetically

Question

So in a class Tournament, I have an ArrayList of that contains (String Name, int handicap)

There is a method alphabeticSort() which sorts the list of players alphabetically by name. I have to use insertion sort for it.

Below I tried to adapt insertion sort algorithm I know to make it work but both lines of

players.add(j+1) 

gives me an error saying "the left hand side of an assignment must be a variable." I understand what that means but I am unable to come up with a solution for it.

    public void alphabeticSort() {

    for(int i = 1; i < players.size(); i++)  {
        String key = players.get(i).getName();
        int j = i - 1;
        while (j >= 0 && key.compareTo(players.get(i).getName()) < 0) {
            players.add(j+1) = players.get(j);

            j--;
        }
        players.add(j+1) = key;
    }

Im not sure how to resolve this. Am I even on the right track? Please help. Any help appreciated

EDIT: I have changed the first instance of

players.add(j+1) = players.get(j);

to

players.set(j+1, players.get(j));

Do I do the same for the second instance (last line)

Also I have found out that the line

 while (j >= 0 && key.compareTo(players.get(i).getName()) < 0)

is wrongs as in the actual insertion sort its supposed to be

 while(j >= 0 && arr[k]> backup)

BUT im not sure how to implement that with Strings, as you cannot use operators on strings. HELP???

EDIT 2:

JUnit test which is supposed to test if it works

public void testAlphabeticSort() {
    int [] par = {3,4,5,4,5,3,4,3,5,3,4,5,4,3,4,5,4,3};
    int [] scores1 = {3,4,3,5,3,4,4,3,5,3,3,4,3,4,3,4,3,4};
    int [] scores2 = {4,4,3,5,3,4,4,3,5,3,3,4,3,4,3,4,3,4};
    int [] scores3 = {3,4,3,5,3,4,4,3,5,3,3,4,3,4,3,4,3,5};
    Tournament T = new Tournament(par);
    T.enter("Scott",  1, scores3);
    T.enter("Norman",  2, scores1);
    T.enter("Palmer",  4, scores2);
    T.alphabeticSort();
    ArrayList<Player> sortedPlayers = T.getPlayers();
    Player player1 = new Player("Norman", 2, scores1);
    Player player2 = new Player("Palmer", 4, scores2);
    Player player3 = new Player("Scott", 1, scores3);
    assertTrue(sortedPlayers.get(0).equals(player1));
    assertTrue(sortedPlayers.get(1).equals(player2));
    assertTrue(sortedPlayers.get(2).equals(player3));
}

Answer 1

There are a few points that I think you should consider about Lists

1. ArrayList<E>, is used to allow fast random read access whereas
2. LinkedList<E> allows for constant-time insertions or removals.

If your program have many insertions and removals, then you should consider using LinkedList instead of ArrayList.

also see: When to use LinkedList over ArrayList?

---

The problem in your code is at players.add(j+1) = players.get(j);. You can only use assignment operator on a variable and NOT a method.

However, if you're willing to set the j+1 value of List players, then you can make use of set() method which is available for both LinkedList and ArrayList.

players.set(j+1, players.get(j));

Answer 2

For the specific error, your line should be modified as:

players.add(j+1, players.get(j));

it will shift the subsequent elements in the list.

If you use set function, it will replace the entity at index j+1

Observe the changes and change the function body like below:

for(int i = 1; i < players.size(); i++)  {
    Player key = players.get(i);
    int j = i - 1;
    while (j >= 0 && key.getName().compareTo(players.get(j).getName()) < 0) {
        players.set(j+1, players.get(j));

        j--;
    }
    players.set(j+1, key);
}

Answer 3

You wrong here: players.add(j+1) = players.get(j);

You cant assigning a values for a method.

Class ArrayList provide 2 methods to add an Object.

In your case: you use add(Object) - it will add an Object in parameter into your ArrayList at last position and return true or false.

To fix your issue: Let use method add(int index, Object object). This method will insert an Object into your ArrayList with index position.

Codes xample:

players.add( j+1, players.get(j) ) ;

Answer 4

You could also implement your own Comparator to keep things clean, i made a little program so you can test it easily

Player:

public class Player
{
    private String name;
    private int handicap;
    
    public Player (String name, int handicap)
    {
        this.name = name;
        this.handicap = handicap;
    }
    /**
     * @return the name
     */
    public String getName ( )
    {
        return name;
    }
    /**
     * @param name the name to set
     */
    public void setName ( String name )
    {
        this.name = name;
    }
    /**
     * @return the handicap
     */
    public int getHandicap ( )
    {
        return handicap;
    }
    /**
     * @param handicap the handicap to set
     */
    public void setHandicap ( int handicap )
    {
        this.handicap = handicap;
    }
}

ComparatorPlayer:

import java.util.Comparator;

public class ComparatorPlayer implements Comparator<Player> {

    @Override
    public int compare(Player p1, Player p2)
    {
        if( p1.getName ( ).compareTo ( p2.getName ( ) ) < 0 )
        {
            return -1;
        }
        else if ( p1.getName ( ).compareTo ( p2.getName ( ) ) > 0 )
        {
            return 1;
        }
        return 0;
    }


}

Console for testing purposes:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Console
{

    public static void main ( String [ ] args )
    {
        List < Player > players = new ArrayList< Player >();
        List < Player > playersOrdered = new ArrayList < Player > ( );
        
        players.add ( new Player ( "Chris", 32222 ) );
        players.add ( new Player ( "John", 3 ) );
        players.add ( new Player ( "Zebra", 5 ) );
        players.add ( new Player ( "Albert", 333 ) );
        players.add ( new Player ( "Chris", 32222 ) );
        players.add ( new Player ( "Chris", 3 ) );

        
        
        Collections.sort ( players, new ComparatorPlayer ( ) );
        
        
        
        for ( Player player : players )
        {
            System.out.println ( player.getName ( ) +  " + " + player.getHandicap ( ) );
            playersOrdered.add ( player );
        }
        
    }

}

Output:

Albert + 333

Chris + 32222

Chris + 32222

Chris + 3

John + 3

Zebra + 5

References:

Comparator

---

EDIT:

I'm sorry that I didn't realize that you had to implement you own sort function. Try this:

Console && alphabeticSort:

import java.util.ArrayList;

public class Console
{

    public static void main ( String [ ] args )
    {
        System.out.println ( "Starting" );
        ArrayList < Player > players = new ArrayList < Player > ( );
        players.add ( new Player ( "John" , 3 ) );
        players.add ( new Player ( "Chris" , 32222 ) );
        players.add ( new Player ( "Zebra" , 5 ) );
        players.add ( new Player ( "Albert" , 333 ) );
        players.add ( new Player ( "Christ" , 32222 ) );
        players.add ( new Player ( "Chris" , 3 ) );

        alphabeticSort ( players );

        for ( Player player : players )
        {
            System.out.println ( player.getName ( ) + " + " + player.getHandicap ( ) );
        }

        System.out.println ( "Finish" );
    }

    // alphabeticSort pass by parameter
    public static void  alphabeticSort ( ArrayList < Player > players )
    {
        int i = 1 , j;
        Player key = new Player ( );
        ArrayList < Player > inputArray = players;

        for ( j = 1 ; j < inputArray.size ( ) ; j ++ )
        {
            key = inputArray.get ( j );
            i = j - 1;
            
            while ( i >= 0 )
            {
                if ( key.getName ( ).compareTo ( inputArray.get ( i ).getName ( ) ) > 0 )
                {
                    break;
                }
                
                Player element = inputArray.get ( i + 1 );
                inputArray.set ( i + 1 , inputArray.get ( i ) );
                inputArray.set ( i , element );
                i -- ;
            }
        }
    }
}

Output:

Starting

Albert + 333

Chris + 3

Chris + 32222

Christ + 32222

John + 3

Zebra + 5

Finish

---

EDIT2 Solution asked by OP:

Here is your solution (JUnit test passed)

Player:

import java.util.Arrays;

public class Player
{
    private String name;
    private int handicap;
    private int scores[];
    
    public Player( )
    {
        
    }
    
    public Player (String name, int handicap)
    {
        this.name = name;
        this.handicap = handicap;
    }
    
    public Player (String name, int handicap, int [] scores)
    {
        this.name = name;
        this.handicap = handicap;
        this.setScores ( scores ); 
    }
    
    /**
     * @return the name
     */
    public String getName ( )
    {
        return name;
    }
    /**
     * @param name the name to set
     */
    public void setName ( String name )
    {
        this.name = name;
    }
    /**
     * @return the handicap
     */
    public int getHandicap ( )
    {
        return handicap;
    }
    /**
     * @param handicap the handicap to set
     */
    public void setHandicap ( int handicap )
    {
        this.handicap = handicap;
    }

    /**
     * @return the scores
     */
    public int [] getScores ( )
    {
        return scores;
    }

    /**
     * @param scores the scores to set
     */
    public void setScores ( int scores[] )
    {
        this.scores = scores;
    }

    /* (non-Javadoc)
     * @see java.lang.Object#hashCode()
     */
    @Override
    public int hashCode ( )
    {
        // TODO Auto-generated method stub
        return super.hashCode ( );
    }

    /* (non-Javadoc)
     * @see java.lang.Object#equals(java.lang.Object)
     */
    @Override
    public boolean equals ( Object obj )
    {
        Player objToCompare = (Player) obj;
        if( this.handicap == objToCompare.getHandicap ( ) &&
                this.name.equals ( objToCompare.getName ( ) ) &&
                    Arrays.equals ( this.scores , objToCompare.scores ))
        {
            return true;
        }
        return false;
        
    }
    
}

Tournament:

import java.util.ArrayList;

public class Tournament
{

    int [] scores;
    ArrayList<Player> players = new ArrayList<Player> ( );
    int [] pars;
    
    public Tournament ( int [ ] par )
    {
        this.pars = par;
    }

    /**
     * @return the scores
     */
    public int [ ] getScores ( )
    {
        return scores;
    }

    /**
     * @param scores the scores to set
     */
    public void setScores ( int [ ] scores )
    {
        this.scores = scores;
    }

    /**
     * @return the players
     */
    public ArrayList < Player > getPlayers ( )
    {
        return players;
    }

    /**
     * @param players the players to set
     */
    public void setPlayers ( ArrayList < Player > players )
    {
        this.players = players;
    }

    /**
     * @return the pars
     */
    public int [ ] getPars ( )
    {
        return pars;
    }

    /**
     * @param pars the pars to set
     */
    public void setPars ( int [ ] pars )
    {
        this.pars = pars;
    }
    
    /**
     * Enter a player to a tournament
     * @param name
     * @param handicap
     * @param scores
     */
    public void enter ( String name , int handicap , int [ ] scores )
    {
        this.players.add ( new Player ( name, handicap, scores ));
    }

    
    /**
     * alphabeticSort by player name
     */
    public void alphabeticSort ()
    {
        int i = 1 , j;
        Player key = new Player ( );
        ArrayList < Player > inputArray = this.getPlayers ( );

        for ( j = 1 ; j < inputArray.size ( ) ; j ++ )
        {
            key = inputArray.get ( j );
            i = j - 1;
            
            while ( i >= 0 )
            {
                if ( key.getName ( ).compareTo ( inputArray.get ( i ).getName ( ) ) > 0 )
                {
                    break;
                }
                
                Player element = inputArray.get ( i + 1 );
                inputArray.set ( i + 1 , inputArray.get ( i ) );
                inputArray.set ( i , element );
                i -- ;
            }
        }
       this.players = inputArray;
    }

}

JUnit:

Answer 5

Here in the above code you are always comparing the value at i with itself. Change it to j and the last statement should be players.set(j+1,key);.

So the final code looks like this.

 for(int i = 1; i < players.size(); i++)  {
    String key = players.get(i).getName();
    int j = i - 1;
    while (j >= 0 && key.compareTo(players.get(j).getName()) < 0) {
        players.set(j+1, players.get(j));

        j--;
    }
      players.set(j+1,key);