Basic Bubble Sort by ArrayList in Java

Question

I implemented a comparator and it did not work, so I thought that I would write the basic view of the bubble.

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 right? https://blog.udemy.com/bubble-sort-java/

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

 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 would really like to get access to several methods (for example, find out why my comparator does not work), but now I just want the Bubble Sort to work correctly. Thanks.

Answer 1

Thanks to everyone who pointed me in the right direction. One problem was that I forgot .trim (), so compareTo did not work and did not compare with charAt (0).

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

This is what works now:

  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 2

This is a strange and inefficient implementation, you are comparing every number that is with each other. Something like this is much more intuitive (you can improve a little in performance, but that’s not the point, you just save a lot of time, don't go wrong with indexes, and if you really care about performance and not readability of mergesort or quicksort, as Java does [Java uses quicksort for primitive types and mergesort for Object, probably because it doesn’t matter for primitive types whether 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); } 

Applies 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 will be true if s contains only characters.

Answer 3

If you write

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

Then you will get ArrayIndexOutOfBoundsException for the next line,

 tempVar = numbers [j + 1]; 

Because the numbers array is 5 in length with the last index of 4 (since the index starts at 0 ). Thus, when j = 4 the loop termination condition j < numbers.length or 4 < 5 is true , but you will get access to the exception by specifying 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 piece of code, can you tell me what exactly the problem is you getting?

From wild guesses, your a.compareTo(b) < 0 does not work the way you want.

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

I am confused by what exactly you want, therefore, it creates the following code that can help you 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); } } 

The output is a list containing:

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

Answer 4

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

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

Read this at the beginning of Bubble sort , as the lesson you mentioned is completely erroneous

Fixed 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 a working link

Answer 5

There is a slight problem with the original sorting program.

 int j=0 

it should be

 int j=i 

Also, you did not replace it for sorting strings.

 a.compareTo(b) < 0 

it should be

 a.compareTo(b) > 0 

Check this:

 import java.util.*; public class HelloWorld{ public static void main(String[] args){ ArrayList<Person> list = new ArrayList<Person>(); list.add(new Person("xyz")); list.add(new Person("abc")); list.add(new Person("pqr")); list.add(new Person("lmn")); String a; String b; Person c; Person d; for (int i=0; i< list.size(); i++){ for(int j=i; 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); } } } for(Person person: list){ System.out.println(person.lastName); } } } class Person{ String lastName; Person(String str){ lastName = str; } public String getLastName(){ return lastName; } } 

Answer 6

 Bubble Sort Swap Printer in JAVA: static void countSwaps(int[] a) { int swaps = 0; for(int i=0; i<a.length-1; i++){ for(int j=0; j<a.length-i-1; j++){ if (a[j] > a[j+1]){ int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; swaps++; } } } System.out.println("Array is sorted in " + swaps +" swaps."); }