Bubble Sort—Java

The bubble sort is a very common algorithm that many computer science students are expected to learn. Yesterday I did a post that shows a Python implementation of the bubble sort which you can view here. Today I will demonstrate the same technique in Java.

import java.util.Arrays;

public class BubbleSort {

public static void main(String [] args){
Integer [] nums = {9, 4, 2, 1, 10};
System.out.println("Unsorted is " + Arrays.toString(nums));

bubbleSort(nums);
System.out.println("Sorted is " + Arrays.toString(nums));
}

public static<T extends Comparable> void bubbleSort(T [] array){
int n = array.length;
T temp;

for(int i = 0; i < n; i++){
for (int j = 1; j  0){
//Swap the elements
temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}
}
}
}
}

Java is a little more verbose than Python. Since it is a statically typed language (which means you have to declare the data type up front, as opposed to Python’s duck typing method), I chose to use generics to implement this sort.

Generics were introduced in JDK 1.5. They allow us to write code that is widely applicable to many types of objects without forcing us to use the Object class. You can find a wide use of generics in the java.util package.

In this case, I declared my generic method like this

public static<T extends Comparable> void bubbleSort(T [] array){

Let’s go through this one word at a time.

  1. public—This is the keyword that makes this method publically available
  2. static—This keyword attaches this method to the class rather than an object
  3. <T extends Comparable>—This is the code that declares this method to be a generic method. T is the type of the object, followed by extends Comparable which means that any object that implements the Comparable interface is accetable to this method.
  4. T [] array—This declares an array of type T (which is any class that implements Comparable in this case)

Now that we have declared this to be a generic method, this method will work with any object that implements the Comparable interface. The Comparable interface is widely used throughout Java in sorting. It declares a compareTo(T obj) method which returns a positive number when an item is greater than the comparing object, zero when the two objects are equal, and a negative number when the comparing object is less than the other object.

Since this interface exists, Java lets us sort anything that implements this interface easily. That allows programmers a high degree of freedom and flexibility when creating custom classes because the programmer gets to decide how one object is greater than, less than, or equal to another object.

We apply the Comparable interface to this bubble sort method here

if(array[j - 1].compareTo(array[j]) > 0){
//Swap the elements
temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}

If the left hand portion array[j - 1].compareTo(array[j]) is 0, then these two items are 0. If the result is a negative number then array[j - 1] is less than array[j], otherwise array[j - 1] is greater than array[j] and it needs to get swapped.

When run, we get this output

Unsorted is [9, 4, 2, 1, 10]
Sorted is [1, 2, 4, 9, 10]
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s