JB Header
Bubble Sort in Java
This tutorial explains Bubble Sort algorithm with an example showing multiple iterations of the algorithm. It then shows how to implement bubble sort in Java and explains the code. What is Bubble Sort: Bubble Sort, considered by many to be the simplest of sorts, works by progressively in-place sorting(ie. not using up extra space while sorting) a list of items by moving the lowest valued item to the to the top or largest valued item to the bottom(for an ascending sort). It keeps lining bigger and bigger elements below the earlier smaller ones. In this way the whole array gets sorted. You can see a whiteboard animation video explanation of how bubble sort works and get a code walk-through in this YouTube video
Bubble Sort's working in detail -Lets say our list to be sorted is [1000, 1, 100, 101, 15].As per bubble sort, we will move progressively the largest valued items to the bottom/end of the list. First Pass of Bubble Sort Algorithm Lets start with the first pass from left to right in the list [1000, 1, 100, 101, 15]. The various comparisons that happen in the first pass are -
  1. 1000 is compared to 1. As 1000>1 it is swapped. The list is now [1,1000,100,101,15].
  2. 1000 is now compared with 100. As 1000 > 100 the two items are swapped. The list now is [1,100,1000,101,15]
  3. 1000 is now compared with 101. As 1000 > 101 they are swapped. The list now is [1,100,101,1000,15]
  4. 1000 is now compared wiuth 15. As 1000>15 they are swapped. The list now is [1,100,101,15,1000]
The first pass is now complete. Note that the largest element in the list(1000) has bubbled to the rightmost and correct place. List at the end of the first pass is [1,100,101,15,1000]. Second Pass We again start from left and move to the right -
  1. 1 is compared with 100. As 1 < 100 nothing is done. List remains [1,100,101,15,1000]
  2. 100 is now compared with 101. As 100 < 101 nothing is done. List remains the same.
  3. 101 is now compared with 15. As 101 > 15 they are swapped. The list now is [1,100,15,101,1000].
The second pass ends at this point as the last element(1000) was already marked as greatest in the first pass. The second-last element(101) is the second largest at the end of the second pass now. List at the end of the second pass is [1,100,15,101,1000]. Further Passes Similar to the first and second pass, passes keep bubbling up largest elements to the right while the size of the unsorted list keeps reducing. After exactly n-1 passes the list is considered to be sorted as all the elements are now in their correct position. [su_box title="Java-based algorithm for Bubble Sort" style="soft" box_color="#fcba43" title_color="#00000" radius="4" Class="for-shortcodebox"][java]package com.javabrahman.algorithms.sorts; public class BubbleSort { static int intArray[] = { 1000, 1, 100, 101, 15 }; public static void doSort() { for (int outer = 0; outer < intArray.length; outer++) { for (int inner = 0; inner < intArray.length - outer- 1; inner++) { if (intArray[inner] > intArray[inner + 1]) { int temp = intArray[inner]; intArray[inner] = intArray[inner + 1]; intArray[inner + 1] = temp; }//if condition ends }//inner loop ends }//outer loop ends } public static void printArray() { for (int i = 0; i < intArray.length; i++) { System.out.print(" " + intArray[i]); } } public static void main(String args[]) { System.out.print("Array Before Sorting->"); printArray(); doSort(); System.out.print("\nArray After Sorting ->"); printArray(); } }[/java][/su_box]  OUTPUT of the above code[su_note note_color="#1a1a1a" text_color="#DAD9D7"] Array Before Sorting-> 1000 1 100 101 15 Array After Sorting -> 1 15 100 101 1000[/su_note] Explanation of the Java-Based Bubble Sort Algorithm
  • The doSort() method in the above java program holds the sorting logic.
  • There are 2 loops. The loop with the counter outer represents the passes and continues for 0 to length - 1 times. ie. 1 less than the number of items times.
  • The loop with the counter inner represents the sorted element being moved/bubbled forward. It continues from 0 to length-outer-1 times. This is because the size of the unsorted part of the array keeps reducing in exact correlation with the number of passes completed i.e number of elements sorted and put in their correct place.
  • The main() method orchestrates the sorting.
  • The instance element intArray[] holds the list to be sorted.
[su_note note_color="#fbfbc4" text_color="#000000" radius="4"][/su_note]