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