### How to implement Bubble Sort in Java

### Bubble Sort

Bubble sort also termed as sinking sort, is simple sorting algorithm which sort the list of data in ascending order by repeatedly stepping into it. In this algorithm, two adjacent element from list is compared and swapped if preceding element is greater than its next element. This will proceed throughout the list until all the elements are arranged into ascending order.

Bubble sort makes multiple passes to get the final result. Below figure shows the first pass-

The number of pairs from ‘N’ number of elements that will be required to compare in first pass is (N-1). Let us see a graphical representation how it is done in first pass-

In the example we’ve five numbers of elements and number of pairs that will be required in first pass is (N-1) i.e. 4. This will go on until we’ve got a sorted series.

Let us see how this can be implemented in Java.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
package com.code2succeed.bubblesort; public class BubbleSort { public static void main(String[] args) { //Create an array with data which is required to be sorted int array[] = new int[]{3,-5,2,6,1}; //print array before sorting using bubble sort algorithm System.out.println("Array Before Bubble Sort"); for(int i=0; i < array.length; i++){ System.out.print(array[i] + ","); } //Sorting the unsorted data using bubble sort algorithm bubbleSort(array); //Array output after sorting the data System.out.println("Array After Bubble Sort"); for(int i=0; i < array.length; i++){ System.out.print(array[i] + " "); } } private static void bubbleSort(int[] array) { int l = array.length; int temp = 0; for(int i=0; i < l; i++){ for(int j=1; j < (l-i); j++){ if(array[j-1] > array[j]){ temp = array[j-1]; array[j-1] = array[j]; array[j] = temp; } } } } } |

#### Output:

1 2 3 4 |
Array Before Bubble Sort 3 -5 2 6 1 Array After Bubble Sort -5 1 2 3 6 |

The number of passes required to complete the sorting is explained below:

Pass | No. of pairs |
---|---|

1 | N-1 |

2 | N-2 |

3 | N-3 |

- | - |

— | — |

N-1 | 1 |

As we can see the number of comparison required on first pass is N-1 and in second it is N-2 and it goes on until it reaches to one. Hence the complexity of Bubble Sort is O(n2).

The bubble sorting is considered to be most inefficient as it is required to make exchange of data before the final location is known. This involves lots of unnecessary exchanges and cost performance.

Advantage of using bubble sort is the simplicity of the algorithm.Space complexity for Bubble Sort is O(1), because only single additional memory space is required for temp variable

Best-case Time Complexity will be O(n), it is when the list is already sorted.