Bubble Sort

Bubble sort also known as Sinking sort, it is a simple sort
algorithm that repeatedly steps through the list to be sorted, compares each
pair of adjacent items and swaps them if they are in the wrong order. The pass
through the list is repeated until no swaps are needed, which indicates that
the list is sorted.  First this algorithm
is named as comparison sort later it is bubble
sort.

Algorithm for Bubble sort:

for
i = 1:n,

    swapped = false

    for j = n:i+1,

        if a[j] < a[j-1],

            swap a[j,j-1]

            swapped = true

    → invariant: a[1..i] in final position

    break if not swapped

end

In
the case of nearly sorted data, bubble sort takes O(n) time, but requires at
least 2 passes through the data (whereas insertion sort requires something more
like 1 pass).

Bubble
sort has worst-case and average complexity both O(n²),
where n is the number of items being sorted. There exist many sorting
algorithms with substantially better worst-case or average complexity of O(n log n).
Even other О(n²) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore, bubble
sort is not a practical sorting algorithm when n is large.

Pseudo
code:

  procedure bubbleSort( A : list of sortable items )

   n = length(A)

   repeat

     swapped = false

     for i = 1 to n-1 inclusive do

       /* if this pair is out of order */

       if A[i-1] > A[i] then

         /* swap them and remember something changed */

         swap( A[i-1], A[i] )

         swapped = true

       end if

     end for

   until not swapped

end procedure



Time complexity of Bubble sort: O(n)

Average Performance: O(n²)

Worst case Performance: O(n²)

Best case performance: O(n)

Worst Case Space complexity: O(n) total, O(1) auxiliary.

Example for Bubble sort:

Let us take the array of numbers
"5 1 4 2 8", and sort the array from lowest number to greatest number
using bubble sort. In each step, elements written in bold are being
compared. Three passes will be required.

First Pass

( 5 1 4 2 8 ) → {\displaystyle \to } (
1 5 4 2 8 ), Here, algorithm compares the first two elements, and
swaps since 5 > 1.

( 1 5 4 2 8 ) →
{\displaystyle \to } (
1 4 5 2 8 ), Swap since 5 > 4

( 1 4 5 2 8 ) →
{\displaystyle \to } (
1 4 2 5 8 ), Swap since 5 > 2

( 1 4 2 5 8 ) →
{\displaystyle \to } (
1 4 2 5 8 ), Now, since these elements are already in order (8
> 5), algorithm does not swap them.

Second Pass

( 1 4 2 5 8 ) → {\displaystyle \to } (
1 4 2 5 8 )

( 1 4 2 5 8 ) →
{\displaystyle \to } (
1 2 4 5 8 ), Swap since 4 > 2

( 1 2 4 5 8 ) →
{\displaystyle \to } (
1 2 4 5 8 )

( 1 2 4 5 8 ) →
{\displaystyle \to } (
1 2 4 5 8 )

Now, the array is already sorted, but the algorithm does not know if it is
completed. The algorithm needs one whole pass without any swap to
know it is sorted.

Third Pass

( 1 2 4 5 8 ) → {\displaystyle \to } (
1 2 4 5 8 )

( 1 2 4 5 8 ) →
{\displaystyle \to } (
1 2 4 5 8 )

( 1 2 4 5 8 ) →
{\displaystyle \to } (
1 2 4 5 8 )

( 1 2 4 5 8 ) → {\displaystyle
\to } (
1 2 4 5 8 )

Program for Bubble sort:

import java.util.Scanner;



class BubbleSort {

  public static void main(String []args) {

    int n, c, d, swap;

    Scanner in = new Scanner(System.in);



    System.out.println("Input number of integers to sort");

    n = in.nextInt();



    int array[] = new int[n];



    System.out.println("Enter " + n + " integers");



    for (c = 0; c < n; c++)

      array[c] = in.nextInt();



    for (c = 0; c < ( n - 1 ); c++) {

      for (d = 0; d < n - c - 1; d++) {

        if (array[d] > array[d+1])

        {

          swap       = array[d];

          array[d]   = array[d+1];

          array[d+1] = swap;

        }

      }

    }



    System.out.println("Sorted list of numbers");



    for (c = 0; c < n; c++)

      System.out.println(array[c]);

  }

}

Output of the Program: