Basic Bubble Sort with ArrayList in Java

Question

I was implementing a comparator, and it wasn't working, so I thought I'd write a basic bubble sort.

int[] numbers = { 5, 8, 14, 1, 5678 };
int tempVar;
for (int i = 0; i < numbers.length; i++)
{
   for(int j = 0; j < numbers.length; j++)
   {
            if(numbers[i] > numbers[j + 1])
            {
                   tempVar = numbers [j + 1];
                   numbers [j + 1]= numbers [i];
                   numbers [i] = tempVar;
            }
   }
}
for (int i = 0; i < numbers.length; i++)
{
     System.out.println(numbers[i].toString());
}

Is this tutorial correct at all? https://blog.udemy.com/bubble-sort-java/

I followed the example and applied it to Last Names in an arraylist, but the results are a bit wack.

String a;
String b;
Person c;
Person d;

for (int i=0; i< list.size(); i++){

    for(int j=0; j< list.size()-1; j++){

         a = list.get(i).getLastName();
         b = list.get(j+1).getLastName();
         c = list.get(i);
         d = list.get(j+1);

         if ( a.compareTo(b) < 0 )  {

             Person temp = d;
             list.set(j+1, c);        
             list.set(i, temp); 
         }
     }
 }

I'd really like to get a grip on a few methods (like figuring out why my comparator didn't work), but right now I'd just like to get a Bubble Sort to work correctly. Thanks.

Answer 1

In Bubble sort you need to compare only the adjacent elements and swap them(depending up on the condition).

If you are doing ascending order than comparing the adjacent elements and swap if(arr[j]>arr[j+1]). This moves the largest elements to the end in the first iteration.Thus there are n-1 iterations in outer loop to sort the array where n is the length of the array.

Read this first Bubble sort as the tutorial you mentioned is completely wrong

Corrected code

for (int i = 0; i < numbers.length-1; i++)
{
   for(int j = 0; j < numbers.length-i-1; j++)
   {
            if(numbers[j] > numbers[j + 1])
            {
                   tempVar = numbers [j + 1];
                   numbers [j + 1]= numbers [j];
                   numbers [j] = tempVar;
            }
   }
}

Here is the working link

Answer 2

This is a strange and inefficient implementation, you compare each number which each other. Something like this is much more intuitive (could be improved a little performance-wise, but that is not the point, you will just save a lot of time not accidently making mistakes with the indices and if you really care about performance and not readability use mergesort or quicksort as Java does [Java is using quicksort for primitive types and mergesort for Objects, probably because for primitive types it doesn't matter if the algorithm is stable or not]):

public void bubbleSort(int[] arr) {
    boolean change;
    do {
        change = false;
        for (int i = 0; i < arr.length - 1; i++) {
             if (arr[i] > arr[i + 1]) {
                 int temp = arr[i];
                 arr[i] = arr[i + 1];
                 arr[i + 1] = temp;
                 change = true;
             }
        }
    } while (change);
}

Applied to your code (sorts ascending):

boolean change;
do {
    change = false;
    for (int i = 0; i < list.size() - 1; i++) {
         c = list.get(i);
         d = list.get(i + 1);
         a = c.getLastName();
         b = d.getLastName();
         // add special comparison for null values if a or b can be null ("" is ok)
         // toLowerCase() is to compare case-insensitive ('a' != 'A')
         if (a.toLowerCase().compareTo(b.toLowerCase()) > 0) {
             list.set(i, d);        
             list.set(i + 1, c);
             change = true;
         }
     }
} while (change);

Sidenote: s.toUpperCase().compareTo(s.toLowerCase()) == 0 would be true if s only contains symbols.

Answer 3

Thanks to everyone for pointing me in the right direction. One problem was I forgot to .trim() so compareTo wasn't working and neither was comparing with charAt(0).

Also, I found a better implementation of loops for Bubble-Sort.

This is what now works:

    String a;
    String b;
    Person c;
    Person d;

    for (int i= 0; i< list.size() ; i++){

        for(int j=0; j< list.size() - i-1; j++){

             a = list.get(j).getLastName().toUpperCase().trim();
             b = list.get(j+1).getLastName().toUpperCase().trim();

             c = list.get(j);
             d = list.get(j+1);

             if ( a.compareTo(b) > 0)  {

                 Person temp = d;  
                 list.set(j+1, c);
                 list.set(j, temp);

             } 
        }

Answer 4

If you write,

for(int j = 0; j < numbers.length; j++)

Then, you will get ArrayIndexOutOfBoundsException for the following line,

tempVar = numbers [j + 1];

Because, the array numbers has length 5 with last index 4 (as index starts from 0). So, when j = 4, the loop breaking condition j < numbers.length or 4 < 5 is true, but you will get exception accessing numbers [4 + 1] index.

So try

for(int j = 0; j < numbers.length -1; j++)

or

for(int j = i; j < numbers.length -1; j++) // more efficient

Now for the second snippet of your code, can you tell me what exactly the problem you get?

From a wild guess, your a.compareTo(b) < 0 is not working like what you want.

Note that compareTo returns a value less than 0 if string a is lexicographically less than the string b.

I'm confused what exactly you want, hence produces the following code which may help you to overcome your problem:

import java.util.ArrayList;

public class Sort{
    private static ArrayList<String> list = new ArrayList<String>();

    public static ArrayList<String> sortByName(String [] input) {
        String temp;
        for (int i=0; i< input.length; i++){
            for(int j= i; j< input.length-1; j++){
                char first = input[i].charAt(0);
                char sec = input[j +1].charAt(0);
                 if (first < sec)  {
                     temp = input[j +1];
                     input[j +1] = input[i];        
                     input[i] = temp;
                 }
             }
            list.add(input[i]);
         }

        return list;
    }

    public static void main(String[] args) {
        String string[] =  {"Ezen", "Allen" , "Wilker", "Kruden", "Crocket"};
        bubbleSortByName(string);
    }
}

Output is a list containing:

list = [Wilker, Kruden, Ezen, Crocket, Allen]