Bubble sort (Java)

From LiteratePrograms

Other implementations: C | CLIPS | C++ | C# | Eiffel | Erlang | Io | Java | Lisp | Smalltalk

This article covers an implementation of bubble sort in Java.

Bubble sort is an inefficient but very simple - perhaps even the simplest - sorting algorithm, which uses one straightforward rule for its work: while there remains an i^th element that is greater than the (i+1)^th element, swap them.

Thus, elements with greater values will 'float' to the end of the array, like bubbles.

Integer arrays

Firstly, let's write a function which sorts a simple array of integer values:

<<integer array sort>>=
public static void bubble_sort(int[] array)
{
	int right_border = array.length - 1;
	do
	{
		int last_exchange = 0;
		for (int i = 0; i < right_border; i++)
		{
			if (array[i] > array[i + 1])
			{
				int temp = array[i];
				array[i] = array[i + 1];
				array[i + 1] = temp;
				last_exchange = i;
			}
		}
		right_border = last_exchange;
	}
	while (right_border > 0);
}

In this function you may see one little improvement over the 'classic' bubble sort. The 'right_border' variable keeps an index to where the last exchange happened at the previous iteration of the 'do' cycle. This variable keeps a right border of the not yet sorted sequence in the array. If it has value of i, it means that no exchanges were made within elements with indices from i to the end of the array. That is possible only if these elements are placed in the correct order, if they are sorted. Thus it is not necessary to check them at the next iteration. It is then simple to decide when to stop sorting - when there were no exchanges at all and the right border is 0 we can say that the array is sorted.

Generic implementation

The generic implementation of bubble sort takes advantages of 'generics' in Java 5: now our function can sort arrays of any reference type that implements the Comparable interface. This interface is needed because there is no other way to decide if one element is greater or less than another while operating with unknown, 'generic', types.

<<generic array sort>>=
public static <T extends Comparable<? super T>> void bubble_sort_generic(T[] array)
{
	int right_border = array.length - 1;
	do
	{
		int last_exchange = 0;
		for (int i = 0; i < right_border; i++)
		{
			if (array[i].compareTo(array[i + 1]) > 0)
			{
				T temp = array[i];
				array[i] = array[i + 1];
				array[i + 1] = temp;
				last_exchange = i;
			}
		}
		right_border = last_exchange;
	}
	while ( right_border > 0 );
}

Files

Let's combine those methods with a test main function to make a working program:

<<BubbleSortExample.java>>=
import java.util.Random;
class BubbleSortExample
{
    integer array sort
    generic array sort
    public static void main(String[] args) {
        // create test array and fill it with random values
        int[] array = new int[1024];
        Random rnd = new Random();       //it randomize the integer
        for (int i = 0; i < array.length; i++)
            array[i] = rnd.nextInt();       //it randomize the integer inside the array
        // sort our array
        bubble_sort(array);
        // check if it really sorted now
        for (int i = 0; i < array.length - 1; i++ ){
             if (array[i] > array[i + 1]){
                 System.out.println("something wrong");
                 return;
             }
        }
        System.out.println("array sorted");
    }
}