Java: Sorting an ArrayList isn't working

Question

I have a piece of code which fills an ArrayList<Integer> with random integers from 10 to 99 (two digit numbers). It is then supposed to iterate through the array and sort it using bubble sort (or exchange sort, to be honest, I'm not quite sure what the difference is). However, the output that I get is really weird. Attached is the code and example output from it.

import java.util.*;

public class SortingAnArrayList
{
    public static void main( String[] args )
    {
        ArrayList<Integer> al = new ArrayList<>();
        Random r = new Random();

        for ( int i = 0; i < 20; i++ )
        {
            int rNum = 10 + r.nextInt(90);
            al.add( rNum );
        }
        System.out.println( "ArrayList before: " + al);
        ArrayList<Integer> sortedAl = sortArrayList(al);
        System.out.println( "ArrayList after : " + sortedAl);
    }

    public static ArrayList<Integer> sortArrayList( ArrayList<Integer> a )
    {
        boolean loop;
        ArrayList<Integer> b = a;
        do
        {
            loop = false;
            for ( int i = 0; i < a.size() - 2; i++ )
            {
                if ( b.get(i) > b.get(i + 1) )
                {
                    loop = true;
                    int temp = b.get(i);
                    b.remove(i);
                    b.add( i, b.get(i+1) );
                    b.remove(i+1);
                    b.add( i+1, temp );
                }
            }
        } while (loop);

        return b;
    }
}

OUTPUT #1

ArrayList before: [45, 33, 75, 51, 91, 93, 54, 91, 90, 38, 31, 85, 15, 33, 61, 51, 83, 36, 48, 18]
ArrayList after : [93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 18]

OUTPUT 2

ArrayList before: [73, 39, 68, 54, 12, 63, 90, 55, 53, 24, 14, 80, 58, 12, 64, 25, 82, 27, 20, 55]
ArrayList after : [12, 12, 20, 55, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 55]

Please help as I'm not quite sure where I went wrong with the code. Thanks!

Possible duplicate of [Sort ArrayList of custom Objects by property](http://stackoverflow.com/questions/2784514/sort-arraylist-of-custom-objects-by-property) — Koshinae, May 02 '16 at 10:35
Hi, we don't do simple "why isn't my code working?" questions on Stackoverflow. But when you `remove` element `i`, `i+1` becomes the new `i`. Instead of removing and adding, use the `set` method (`b.set(i, b.get(i+1)); b.set(i+1, temp);`. — Cephalopod, May 02 '16 at 10:36

iibrahimbakr · Answer 1 · 2016-05-02T10:55:47.440

What about Collections :

Collections.sort(al);

Your main thread will be:

public static void main(String[] args) {
    ArrayList<Integer> al = new ArrayList<>();
    Random r = new Random();

    for (int i = 0; i < 20; i++) {
        int rNum = 10 + r.nextInt(90);
        al.add(rNum);
    }
    System.out.println("ArrayList before: " + al);
    Collections.sort(al);
    System.out.println("ArrayList after : " + al);
}

score 1 · Answer 2 · answered May 02 '16 at 10:37

1

It should be like this:

loop = true;
int temp = b.get(i);
b.remove(i);
b.add( i, b.get(i) );
b.remove(i+1);
b.add( i+1, temp );

When you call b.remove(i), you decrease indexes after i by 1.

answered May 02 '16 at 10:37

uoyilmaz

3,035
14
25

Also, for ( int i = 0; i < a.size() - 1; i++ ) not for ( int i = 0; i < a.size() - 2; i++ ) – uoyilmaz May 02 '16 at 10:43

Simulant · Answer 3 · 2016-05-02T10:48:21.343

b.add( i, b.get(i+1) );

should be

b.add( i, b.get(i) );

because by b.remove(i); in the line before every item behind the position i is shifted one position to the left an thereby changes it index by -1. This is because you are working on a List. Your implementation should work on an array where the position is not shifted on a remove.

You should read the documentation about remove of the List interface.

Removes the element at the specified position in this list (optional operation). Shifts any subsequent elements to the left (subtracts one from their indices). Returns the element that was removed from the list.

score 1 · Answer 4 · answered May 02 '16 at 10:42

The intention is to swap the two, causing more ordering. This can best be done swapping just the values, as:

                int temp = b.get(i);
                b.set(i, b.get(i+1));
                b.set(i+1, temp);

Removing the i-th element causes that get(i+1) now is another, next integer.

score 1 · Answer 5 · answered May 02 '16 at 10:43

Use this code. I have tested it:

public static ArrayList<Integer> sortArrayList( ArrayList<Integer> a )
    {
    boolean loop;
    ArrayList<Integer> b = a;
    do
    {

        loop = false;
        for ( int i = 0; i < a.size() - 2; i++ )
        {
            if ( b.get(i) > b.get(i + 1) )
            {
                loop = true;
                int temp = b.get(i);
//              b.remove(i);
                b.set( i, b.get(i+1) );
//              b.remove(i+1);
                b.set( i+1, temp );
            }
        }
        System.out.println( "ArrayList b : " + b);
    } while (loop);

    return b;
}

OUTPUT:

ArrayList before: [81, 46, 89, 39, 80, 15, 40, 32, 75, 13, 82, 45, 97, 25, 62, 61, 17, 18, 18, 54]
ArrayList after : [13, 15, 17, 18, 18, 25, 32, 39, 40, 45, 46, 61, 62, 75, 80, 81, 82, 89, 97, 54]

score 1 · Answer 6 · answered May 02 '16 at 10:43

Do not call remove and add, since this has to copy all the remaining elements. Just use set(index, value);

loop = true;
int temp = b.get(i);
b.set( i, b.get(i+1) );
b.set( i+1, temp );

Or, since set returns the previous value:

loop = true;
b.set(i, b.set(i+1, b.get(i)));

score 0 · Answer 7 · answered May 02 '16 at 11:14

0

you should call add() before remove()，like this：

    loop = true;
    int temp = b.get(i);
    b.add( i, b.get(i+1) );
    b.remove(i+1);
    b.add( i+1, temp );
    b.remove(i+2);

however using set() is the best choice.

answered May 02 '16 at 11:14

gogotanc

1
1

Java: Sorting an ArrayList isn't working

7 Answers7