Implementing Bubble Sort algorithm in Java

Bubble sort is a simple algorithm to sort elements of an array. Conventionally it is taught in schools and colleges to introduce students to sorting algorithms but practically it is not suitable for large arrays because of its poor performance. In this post, I will explain bubble sort and how to implement it in Java programming language.

Bubble sort iterates through elements of the arrays, comparing them and swapping if necessary. For example, consider an array of five integer values as below

The first element in this array is 4 and second, 3. In this case, since 4 is greater than 3 you swap them. The array will then become

Next comparison is between the second element (4) and the 3rd element (5). Since 5 is greater than 4 we do not swap and move on to the next element.

Then compare third and fourth elements (5 and 1). 5 greater than 1, so we swap.

Finally, compare the fouth element(5) and the last element(2), and swap since 5 greater than 2.

This completes one pass through the array and you have the largest number of the array in the last position. Now you repeat the process starting again from the first element of the array moving up to the second last element. The last element is skipped as it is already sorted and placed in its correct position.

Pseudocode

The pseudocode for bubblesort algorithm is as below.

Input = array of integers A[]
Output = sorted array A[]

N = length[A]
for pass = 1 to N-1 do

   for index = 0 to N-1-pass do

      if A[index] > A[index+1] then
         temp = A[index]
         A[index] = A[index+1]
         A[index+1] = temp
      end if

   next index

next pass

Java Program for Bubble Sort

The Sor class contains the following methods and attributes.

• main : The main method is the entry point and here you define a new array and intialize it random integer elements. Inside the main method you also call other methods to sort the array and print result.
• printArray : The printArray method takes an array as argument and simply prints its elements.
• bubbleSort : The bubbleSort method sorts an integer array in ascending order using bubble sort algorithm.
• bubbleSort : Method to swap two elements of an array. The swap method takes three arguments - an array and the indexes of the elements to be swapped.
• comparisons, swaps : This program additionally uses two global variables - comparisons and swaps. These are used to count the number of comparisons and swaps required to sort an array and gives you an indication of the time complexity of sorting alorithms.

public class Sort{

    // Global variable to count comparisons and swaps
    private static int comparisons; 
    private static int swaps; 
    
     /**
     * The swap method swaps the contents of two elements in an int array.
     *
     * @param array containing the two elements.
     * @param a     The subscript of the first element.
     * @param b     The subscript of the second element.
     */
    private static void swap(int[] array, int a, int b) {
        int temp;

        temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    /**
     * Sort array using Bubble Sort algorithm
     *
     * @param A array to be printed
     */
    public static void bubbleSort(int[] A) {
         
        int n = A.length;
        comparisons = 0;
        swaps = 0;
        // The outer loop is incremented by 1 for each pass
        for (int pass = 1; pass < n; pass++) {
            // The inner loop steps through each array element,
            // comparing it with its neighbour. if the elements are
            // not in the correct order then they are swapped.
            for (int index = 0; index < n - pass; index++) {
                comparisons++;
                // Compare an element with its neighbour.
                if (A[index] > A[index + 1]) {
                    // Swap the two elements.
                    swap(A, index, index + 1);
                    swaps++;
                }
            }
        }
    }
    
    /**
     * Print an array to the Console
     *
     * @param A array to be printed
     */
    public static void printArray(int[] A) {
        for (int i = 0; i < A.length; i++) {
            System.out.printf("%5d ", A[i]);
        }
        System.out.println();
    }
    
     /**
     * Program Main 
     */
     public static void main(String []args){
        int size = 10;
        int[] A = new int[size];

        // Create random array with elements in the range of 0 to SIZE - 1;
        for (int i = 0; i < size; i++) {
            A[i] = (int) (Math.random() * 100);
        }
        
        // Print input array
        System.out.printf("Input array is\n");
        printArray(A);
        
        // Call bubble sort
        bubbleSort(A);
        
        // Print sorted array
        System.out.printf("Sorted array is \n");
        printArray(A);
        System.out.printf("Number of comparisons: %d \n",comparisons);
        System.out.printf("Number of swaps: %d \n",swaps);
     }
}

Sample output

Here is a sample output from the program.

Input array is
   35    73    35    91    23    19    76    24    38    14 
Sorted array is 
   14    19    23    24    35    35    38    73    76    91 
Number of comparisons: 45 
Number of swaps: 28 

• Rate it
• 
• 
• 
• 

Related Articles

Nothing yet..be the first to share wisdom.