Bubble Sort - Java Code

A stable, in-place, comparison sort.

Two versions:

• Version 1
• Worst case time complexity: O(n²)
• Best case time complexity: O(n²)
• Improvised Version 2
• Worst case time complexity: O(n²)
• Best case time complexity: O(n)

Algorithm

Algorithm bubbleSort ( A )

     Input array A of integers
     Output sorted array A

     n = length (A)

     for i  ← 0 to n - 1 do

            for j ← 0 to n - i - 1 do
if  A[ j ] > A[ j + 1]) then
swap ( A[ j ], A[ j + 1])

Version 1 Java Code

public void bubbleSort(int[] arr) {

              int n = arr.length;

              for (int i = 0; i < n; i++) {

                     for (int j = 0; j < n - i - 1; j++) {

                           if (arr[j] > arr[j + 1]) {

                                  swap(arr, j, j + 1);

                           }

                     }

              }

       }

       public static void swap(int[] arr, int i, int j) {

              int temp = arr[i];

              arr[i] = arr[j];

              arr[j] = temp;

       }

Improvised Version 2 Java Code

public void bubbleSort(int[] arr) {

              boolean swappedOnPrevRun = true;

              int i = 0;

              while (swappedOnPrevRun) {

                     swappedOnPrevRun = false;

                     for (int j = 0; j < arr.length - i - 1; j++) {

                           if (arr[j] > arr[j + 1]) {

                                  swap(arr, j, j + 1);

                                  swappedOnPrevRun = true;

                           }

                     }

                     i++;

              }

       }

       public void swap(int[] arr, int i, int j) {

              int temp = arr[i];

              arr[i] = arr[j];

              arr[j] = temp;

}