The Bubble Sort algorithms in is one of the commonly used algorithm for sorting the data.
Bubble Sort Complexities
Time Complexity
Best Case = O(n)
Average Case = O(n²)
Worst Case = O(n²)
Space Complexity = O(1)
The Bubble Sort algorithm works as follows:
- Start at the left end of the line
- Compare the value of index [0] and [1]
- If the value of the left index[0] is greater then swap them
- If the value of the right index[1] is greater, don’t do anything. Then move over one position to right and compare the values of index positions of [1] and [2]. Again, if the value of the left index is greater, swap them.
Sample Java Programs For Bubble Sort
package com.learning.algorithm.bubbleSort;
public class BubbleSortMain {
public static void main(String[] args) {
int maxSize = 50; // array max size
BubbleSortTest bubbleSortTest; // reference to BubbleSortTest
bubbleSortTest = new BubbleSortTest(maxSize); // create the BubbleSortTest array with maximum size
bubbleSortTest.insert(65); // insert some values into BubbleSortTest array
bubbleSortTest.insert(01);
bubbleSortTest.insert(00);
bubbleSortTest.insert(54);
bubbleSortTest.insert(21);
bubbleSortTest.insert(52);
bubbleSortTest.insert(19);
bubbleSortTest.insert(57);
bubbleSortTest.insert(18);
bubbleSortTest.insert(16);
bubbleSortTest.bubbleSort(); // perform bubble sorting on inserted data
}
}
package com.learning.algorithm.bubbleSort;
public class BubbleSortTest {
private long[] longValueArray; // reference to array
private int items; // number of data items
/*
* Parameterized constructor of BubbleSortTest class
*/
public BubbleSortTest(int max) {
longValueArray = new long[max]; // create an array with provided value
items = 0; // set data items to zero
}
/*
* perform bubble sorting on unsorted data
*/
public void bubbleSort() {
int outerLoop, innerLoop;
System.out.println("Unsorted Input Values.... ");
display(); // print unsorted array values once
for (outerLoop = items - 1; outerLoop > 1; outerLoop--) { // iterate the outer loop in backward order
for (innerLoop = 0; innerLoop < outerLoop; innerLoop++) { // iterate the inner loop in forward order
if (longValueArray[innerLoop] > longValueArray[innerLoop + 1]) { // check if left index value is greater than left+1 index's value
swap(innerLoop, innerLoop + 1); // swap them
}
}
}
}
/*
* swap the values after compare
*/
private void swap(int innerLoopIndex, int innerLoopPlusOneIndex) {
System.out.println("\nSwap value = " + longValueArray[innerLoopPlusOneIndex] + " at index [" + innerLoopIndex
+ "] with value = " + longValueArray[innerLoopIndex] + " at index [" + innerLoopPlusOneIndex + "]");
long temp = longValueArray[innerLoopIndex];
longValueArray[innerLoopIndex] = longValueArray[innerLoopPlusOneIndex];
longValueArray[innerLoopPlusOneIndex] = temp;
display(); //print the array after swapping the values
}
/*
* insert the index value into the array
*/
public void insert(long value) {
longValueArray[items] = value; // insert the value in array
items++; // increment size
}
/*
* display the array contents
*/
public void display() {
for (int j = 0; j < items; j++) // iterate for each element
System.out.print(longValueArray[j] + " \t"); // print the value
System.out.println("");
}
}
Program Output
Unsorted Input Values....
65 1 0 54 21 52 19 57 18 16
Swap value = 1 at index [0] with value = 65 at index [1]
1 65 0 54 21 52 19 57 18 16
Swap value = 0 at index [1] with value = 65 at index [2]
1 0 65 54 21 52 19 57 18 16
Swap value = 54 at index [2] with value = 65 at index [3]
1 0 54 65 21 52 19 57 18 16
Swap value = 21 at index [3] with value = 65 at index [4]
1 0 54 21 65 52 19 57 18 16
Swap value = 52 at index [4] with value = 65 at index [5]
1 0 54 21 52 65 19 57 18 16
Swap value = 19 at index [5] with value = 65 at index [6]
1 0 54 21 52 19 65 57 18 16
Swap value = 57 at index [6] with value = 65 at index [7]
1 0 54 21 52 19 57 65 18 16
Swap value = 18 at index [7] with value = 65 at index [8]
1 0 54 21 52 19 57 18 65 16
Swap value = 16 at index [8] with value = 65 at index [9]
1 0 54 21 52 19 57 18 16 65
Swap value = 0 at index [0] with value = 1 at index [1]
0 1 54 21 52 19 57 18 16 65
Swap value = 21 at index [2] with value = 54 at index [3]
0 1 21 54 52 19 57 18 16 65
Swap value = 52 at index [3] with value = 54 at index [4]
0 1 21 52 54 19 57 18 16 65
Swap value = 19 at index [4] with value = 54 at index [5]
0 1 21 52 19 54 57 18 16 65
Swap value = 18 at index [6] with value = 57 at index [7]
0 1 21 52 19 54 18 57 16 65
Swap value = 16 at index [7] with value = 57 at index [8]
0 1 21 52 19 54 18 16 57 65
Swap value = 19 at index [3] with value = 52 at index [4]
0 1 21 19 52 54 18 16 57 65
Swap value = 18 at index [5] with value = 54 at index [6]
0 1 21 19 52 18 54 16 57 65
Swap value = 16 at index [6] with value = 54 at index [7]
0 1 21 19 52 18 16 54 57 65
Swap value = 19 at index [2] with value = 21 at index [3]
0 1 19 21 52 18 16 54 57 65
Swap value = 18 at index [4] with value = 52 at index [5]
0 1 19 21 18 52 16 54 57 65
Swap value = 16 at index [5] with value = 52 at index [6]
0 1 19 21 18 16 52 54 57 65
Swap value = 18 at index [3] with value = 21 at index [4]
0 1 19 18 21 16 52 54 57 65
Swap value = 16 at index [4] with value = 21 at index [5]
0 1 19 18 16 21 52 54 57 65
Swap value = 18 at index [2] with value = 19 at index [3]
0 1 18 19 16 21 52 54 57 65
Swap value = 16 at index [3] with value = 19 at index [4]
0 1 18 16 19 21 52 54 57 65
Swap value = 16 at index [2] with value = 18 at index [3]
0 1 16 18 19 21 52 54 57 65