Bubble Sort in Java | Sinking Sort Technique

Bubble Sort in Java | Sinking Sort Technique

Bubble sort, sometimes referred to as sinking sort, is a simple sorting 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 algorithm, which is a comparison sort, is named for the way smaller or larger elements "bubble" to the top of the list. Although the algorithm is simple, it is too slow and impractical for most problems even when compared to insertion sort. It can be practical if the input is usually in sorted order but may occasionally have some out-of-order elements nearly in position.

1) Easy to understand.
2) Easy to implement.
3) In-place, no external memory is needed.
4) Performs greatly when the array is almost sorted (This is part of Optimized Bubble Sort).
5) Widely used by students to clear practical exams or freshers interview process as the end result is same as that of any sorting technique

Example Simulation:

An example of bubble sort. Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order (the latter one is smaller than the former one). After each iteration, one less element (the last one) is needed to be compared until there are no more elements left to be compared.

Algorithm (Source):

procedure bubbleSort( A : list of sortable items )
    n = length(A)
   Outer: for (int i = 0; i < n; i++) then
 Inner: for (int j = 0; j < n; j++) then
             if (A[i] < A[j]) then
                /* swap them and remember something changed */
                swap( A[i], A[j] )
            end if
        end for inner
    end for outer
end procedure 

Bubble Sort Program in Ascending Order:

package com.adeepdrive.swap.numbers;
public class BubbleSort {
 public static void main(String[] args) {
  int values[] = { 30, 10, 40, 90, 50 };
  int length = values.length;
  System.out.println("Before sorting ");
  for (int value : values) {
   System.out.print(" " + value);
  }
  System.out.println();
  for (int i = 0; i < length; i++) {
   for (int j = 0; j < length; j++) {
    if (values[i] < values[j]) {
     int temp = values[i];
     values[i] = values[j];
     values[j] = temp;
    }
   }
               System.out.print("For outer loop i value : "+i+" : ");
   for (int value : values) {
    System.out.print(" " + value);
   }
   System.out.println();
               }
  System.out.println("After sorting in Ascending Order");
  for (int value : values) {
   System.out.print(" " + value);
  }
 }
}

Output:

Before sorting
 30 10 40 90 50
For outer loop i value : 0 :  90 10 30 40 50
For outer loop i value : 1 :  10 90 30 40 50
For outer loop i value : 2 :  10 30 90 40 50
For outer loop i value : 3 :  10 30 40 90 50
For outer loop i value : 4 :  10 30 40 50 90
After sorting in Ascending Order
 10 30 40 50 90

Bubble Sort Program in Descending Order:

To get sorted in descending order, Just do the below change in the above program.

if (values[i] > values[j]) {

Output:

Before sorting
 30 10 40 90 50
For outer loop i value : 0 :  10 30 40 90 50
For outer loop i value : 1 :  30 10 40 90 50
For outer loop i value : 2 :  40 30 10 90 50
For outer loop i value : 3 :  90 40 30 10 50
For outer loop i value : 4 :  90 50 40 30 10
After sorting in Descending Order
 90 50 40 30 10

Drawbacks of bubble sort are

1) we have to traverse the input array till the last element.
2) Very expensive, O(n2) in worst case and average case.
3) It does more element assignments than its counterpart, insertion sort.

In next tutorial, We will learn how we can optimize bubble sort for largest arrays.