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));
}

have you Googled 'java insertion sort'? there's lots of examples that can guide you in the right direction — Jayce444, Nov 02 '16 at 03:48
Your algorithm is incorrect (try looking up examples), but that aside, the method you're looking for to update a specific index in the array is `players.set(index, value)`. — Zarwan, Nov 02 '16 at 03:53
@Jayce444 I have, but Im not sure how to apply in an arrayList of strings scenario — Alonzo Robbe, Nov 02 '16 at 03:58
@Zarwan Thanks, Ill look into it. Is the 'players.set' thing the only thing thats missing, apart from the incorrect algorithm? — Alonzo Robbe, Nov 02 '16 at 03:59
It should help you fix the lines `players.add(j+1) = players.get(j)` and `players.add(j+1) = key`. — Zarwan, Nov 02 '16 at 04:04
Just to clarify something: you are **not** sorting "alphabetically", you are sorting by codepoint. This means that "z100" comes before "z2". To sort "alphabetically" (naturally) instead of "ASCIIbetically" you would have to implement your own `Comparator`, but I expect that this isn't terribly important to your task, but I feel it's still an important distinction in general. — Socratic Phoenix, Nov 02 '16 at 04:15

score 2 · Answer 1 · edited May 23 '17 at 12:16

2

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

ArrayList<E>, is used to allow fast random read access whereas
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));

edited May 23 '17 at 12:16

Community

1
1

answered Nov 02 '16 at 04:10

Raman Sahasi

30,180
9
58
71

Thanks, but Ive been told to use ArrayList as its for a school thing. As for the fix, am I supposed to use it both times? – Alonzo Robbe Nov 02 '16 at 04:22
@RobBor yes. You should change that line to `players.set(j+1, key);` – Raman Sahasi Nov 02 '16 at 04:24
It then creates another error and wants me to 'change type of key to player' – Alonzo Robbe Nov 02 '16 at 04:27
@RobBor obviously, you can insert things in `List players` only of similar type. The type of `key` should be that of all the other things in `List players` – Raman Sahasi Nov 02 '16 at 04:30
But if I do that, it kinda messes up everything else I have. And I dont know what to do from there – Alonzo Robbe Nov 02 '16 at 04:33
Actually, Ive sort of fixed it. Its just the `while` statement that needs fixing I think. Would you happen to know how to amend that? I have (with the fixes you provided) `while (j >= 0 && key.getName().compareToIgnoreCase(players.get(j).getName()) > 0)` I feel like its the second condition (after &&) thats messed up, but I dont know how to correct it – Alonzo Robbe Nov 02 '16 at 04:37
I think, in your code, you should change `key.compareTo(players.get(i).getName())` to `key.compareTo(players.get(j).getName())` – Raman Sahasi Nov 02 '16 at 04:44
Yeah, Ive changed i to j, and changed it to `key.getName()` to match `player.get(j).getName()`. I think the problem lies within `> 0`maybe? Is that the correct operator and condition? – Alonzo Robbe Nov 02 '16 at 04:48
the logic seems to be fine. What problem are you facing now? – Raman Sahasi Nov 02 '16 at 05:08
It just doesnt work :/ . I have edited the JUnit test I was provided into the main post. It fails at `T.alphabeticSort();` – Alonzo Robbe Nov 02 '16 at 05:58

Shafiul · Answer 2 · 2016-11-02T10:31:18.593

0

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);
}

edited Nov 02 '16 at 10:31

answered Nov 02 '16 at 04:00

Shafiul

1,452
14
21

For both instances? – Alonzo Robbe Nov 02 '16 at 04:22
check the function body – Shafiul Nov 02 '16 at 10:06
Hmm doesnt seem to work. I have a JUnit test edited in the main post, and it runs for like 12 seconds before returning error. I even tried changing the `<0` to `>0` and still no dice – Alonzo Robbe Nov 02 '16 at 10:23

score 0 · Answer 3 · answered Nov 02 '16 at 04:02

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) ) ;

score 0 · Accepted Answer · edited Jun 20 '20 at 09:12

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 + 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:

While I really do appreciate this, I have to use insertion sort as its for a school thing. Thanks a lot for this tho — Alonzo Robbe, Nov 02 '16 at 04:19
Thanks a lot again! Would you happen to know how to make it work with a non-parameterised version? — Alonzo Robbe, Nov 02 '16 at 06:00
Basically a method to alphabetically (insertion) sort an ArrayList of players when called. Also no parameters are passed through it.i.e. youve got `ArrayList < Player > players` as parameters. So in the main method its just callled `alphabeticSort()`. Ive edited a JUnit test to test the method in the main post aswell. — Alonzo Robbe, Nov 02 '16 at 06:59
@RobBor Check my last solution, i'm going to bed so hurry up if you need anything else. I tried to implement your solution inferring from JUnit your methods. — Rcordoval, Nov 02 '16 at 07:02
Im gettin an error at `this.setPlayers` in the last line. "The method setPlayers(ArrayList) is undefined for the type Tournament" — Alonzo Robbe, Nov 02 '16 at 07:05
Now the JUnit stops at the first `assertTrue` statement. I dunno, I dont want to keep you up. I'll figure out eventually I hope. Thank you for all your help, maybe when you wake up you'll get another idea/answer? Thanks for now bro — Alonzo Robbe, Nov 02 '16 at 07:12
I'm 100% sure that is working, i tested it even with console and changing values, try copy/paste and then edit according to your needs. That is the correct answer. — Rcordoval, Nov 02 '16 at 07:15
I created a pastebin: http://pastebin.com/wnkxUJFx if you want to look at everything. There are 2 classes, Player and Tournament which I forgot to mention so maybe thats messing it up? — Alonzo Robbe, Nov 02 '16 at 07:21
@RobBor I dont know why i post a solution if you dont use it, i spent my time debugging your pastebin just to realize you didn't use my player equals implementation. You can't compare Strings with ==, you need to use `compareTo`. Please paste my equals and your test will pass right away. I tested it. So please, mark my answer as the correct. — Rcordoval, Nov 02 '16 at 07:54
My bad. I used your player equals implementation, and it worked. However, I am not allowed to import other utilities, so `import.java.Arrays` and `Arrays.equals...` cannot be used either. So, i cannot really use your answer. Sorry for all these crazy restrictions, its what my teacher specified. — Alonzo Robbe, Nov 02 '16 at 09:40
Your equalArrays implementation is just fine. You can use it, I just tested it. Anyway the correct answer doesn't have to be the exact answer, but who lead to the solution also. — Rcordoval, Nov 02 '16 at 10:39

score 0 · Answer 5 · answered Nov 02 '16 at 05:21

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);

How to insertion sort an ArrayList of Strings alphabetically

5 Answers5

Player:

ComparatorPlayer:

Console for testing purposes:

Output:

References:

EDIT:

Console && alphabeticSort:

Output:

EDIT2 Solution asked by OP:

Player:

Tournament:

JUnit: