# Implementing Bubble Sort algorithm in Java

Posted on 20th February 2021

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

 4 3 5 1 2

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

 3 4 5 1 2

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.

 3 4 5 1 2

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

 3 4 1 5 2

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

 3 4 1 2 5

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
```