Bubble Sort Algorithm in Java

The bubble sort algorithm makes several passes through the list. On each pass, successive neighboring pairs are compared. If a pair is in decreasing order, its values are swapped; otherwise, the values remain unchanged. The technique is called a bubble sort, because the smaller values gradually “bubble” their way to the top and the larger values sink to the bottom. After first pass, the last element becomes the largest in the list. After the second pass, the second-to-last element becomes the second largest in the list. This process is continued until all elements are sorted.

Below figure shows Bubble Sort illustration with its various passes:

Bubble Sort illustration


Now the same iterations (algorithm) are discussed in below code Listing: 

BubbleSort.java

public class BubbleSort {
       /** Bubble sort method */

       public static void bubbleSort(int[] list) {
              boolean needNextPass = true;

              for (int k = 1; k < list.length && needNextPass; k++) {
                     // Array may be sorted and next pass not needed
                     needNextPass = false;
                     for (int i = 0; i < list.length - k; i++) {
                          if (list[i] > list[i + 1]) {
                               // Swap list[i] with list[i + 1]
                               int temp = list[i];
                               list[i] = list[i + 1];
                               list[i + 1] = temp;
                               needNextPass = true; // Next pass still needed
                          }
                     }
              }
       }

       public static void main(String[] args) {
              int[] list = { 2, 9, 5, 4, 8, 1 };
              bubbleSort(list);
              for (int i = 0; i < list.length; i++)
                     System.out.print(list[i] + " ");
       }
}
 
The output of the program will be:

    1 2 4 5 8 9 


Reference(s): Introduction to JAVA by Y. Daniel Liang

Newer Post Older Post

Leave a Reply

naeemgik. Powered by Blogger.