Java has many sorting techniques which even includes the sort() function of Array and Collections. In addition, we can also implement multiple data structure sorting algorithms in Java such as Bubble sort, Insertion Sort, Merge sort etc.
Sorting in Java is so common that even language beginners have to be expert in it. As in real world, we have to sort some list of things here and there. It is also very often used in Java. Java has Collections and collections needs to be sorted in many cases.
Suppose, you have a collection of Students’ roll numbers. These are stored in an ArrayList. Now, you want this list to be sorted in ascending or descending order for various reasons. Although, there are many ways to do sorting in Java but in this article we are explaining only one.
We are keeping things simple and just focusing on one Bubble Sort.
Introduction to the Bubble Sorting
Bubble sort in Java is one of the simplest sorting algorithm. It is a comparison based algorithm which simply compares the adjacent elements and swap those if they are unsorted. Bubble sort repeats this process until the complete data set is sorted.
As easy as it sounds. It has a bit higher complexity for large data sets. Of course, if you are going to compare every adjacent element repeatedly for a very large data set, it is going to take hell lot of time.
Bubble sort complexity is O(n2). So do not consider it for large data.
Some Important points :
- Bubble sort is one of the simplest algorithm.
- It sorts based on comparison of adjacent elements.
- This is not recommended for large data sets.
- It provides worst and average case complexity of Ο(n2) [n denoted number of items in the data set].
Bubble Sort is idle for small set of elements. It is not recommended for big list of elements.
Understand the Working of Bubble Sort
Ok, we now know the bubble sort mechanism is to compare adjacent elements and then arrange them in order. Let’s understand the working of bubble sorting in Java using one simple example:
Suppose, we have a data set of five items and we need to sort this using bubble sort. The data set of elements is: [3 , 6 , 4 , 7 , 2 ]. Let’s sort this in ascending order using bubble sort.
Input: [3 , 6 , 4 , 7 , 2 ]
First Pass
First of all the bubble sort mechanism will compare the first two elements and will arrange in it correct order if needed. Here, 6 is greater than 3 so no swapping is needed. elements will be same as earlier.
Result: [3 , 6 , 4 , 7 , 2 ]
This time, it will compare the next two elements: 2nd and 3rd. As, 4 is less than 6 we need to swap these two to maintain the correct ordering.
Result: [3 , 4 , 6 , 7 , 2 ]
Similarly, next elements are compared. 7 is greater than 6 so no swapping needed. Result is similar as earlier.
Result: [3 , 4 , 6 , 7 , 2 ]
Time to compare the final elements and sort them if needed. 2 is less than 7 so swapping of these two is needed. The result will be like this:
Result: [3 , 4 , 6 , 2 , 7]
Now, we have completed first round of bubble sorting but you can clearly see that the list is still not sorted. The reason is simple, we need to repeat this process until all elements are sorted. Whenever, the whole pass does not require any swapping then the bubble sort is done.
Second Pass
Now, we will repeat the same process for this pass and sort the list. Let’s try to sort the list step by step again:
Now, 4 is greater than 3 so no swapping is needed. These items of list are already in ascending order. so the list remains same in this step.
Result: [3 , 4 , 6 , 2 , 7]
Similarly, 6 is greater than 4 so these two will not be swapped and 2 is less than 6 so 2 will be swapped with 6 and 7 is greater than 6 so items will not be swapped. Now, we will have list as below.
Result: [3 , 4 , 2 , 6 , 7]
Third Pass
Same steps are performed in this pass too because the complete list is still not in ascending order. Steps are as follows:
The element 4 is greater than 3 so no swapping for these two elements, 2 is less than 4 so 2 and 4 will be swapped, 6 is greater than 4 so no swapping, and 7 is greater than 6 so no swapping for these two as well. The resulted list is as follows:
Result: [3 , 2 , 4 , 6 , 7]
Fourth Pass
The element 2 is less than 3 so 2 and 3 are swapped, 4 is greater than 3 so elements will remain same, again 6 is greater than 4 so swapping is not needed, and 7 is greater than 6 so again no swapping.
Result: [2 , 3 , 4 , 6 , 7]
Now, we can see that the array is already sorted, but our algorithm will take one more step to know if it is completed. The Bubble Sort algorithm needs one whole pass without any swap to know that the list is sorted. So it will run one more pass and as there will not be any swapping it will stop this process and consider the final list as sorted.
Output: [2 , 3 , 4 , 6 , 7]
Java Pseudo Code for Bubble Sort
Let’s write and understand the pseudocode of Bubble Sorting in Java. As you already know, pseudo code is informal code which represents how the program will be written. Instead of machine readable, it is human readable.
Pseudo code for java Bubble sort will be very simple. However, we will optimize it a little to improve the performance. We have added a flag isSwapped to improve the performance as it will break the loop in case no swapping is happened(because it means array or list is already sorted).
We have a procedure bubbleSort which represent the core logic of bubble sorting. There are two loops one to iterate the whole list and another is to iterate each item in the list. we have a flag isSwapped, which represents whether the element is swapped or not. Finally, we have a swap method to swap the passed two elements.
procedure bubbleSort( dataset : array of elements )
length = dataset.count;
for i = 0 to length-1 do:
isSwapped = false
for j = 0 to length-1 do:
if dataset[j] > dataset[j+1] then
swap( dataset[j], dataset[j+1] )
isSwapped = true
end if
end for
if(not isSwapped) then
break
end if
end for
end procedure return datasetBubble Sort Algorithm
Bubble Sort algorithm is not limited to Java rather it is suited for almost every programming language. The reason is simple, the algorithm is based on the data structure bubble sort. In below algorithm, elements represents the list or array which have n data items. These data items needs to be sorted. We have a swapFunction which swaps the passing two elements.
begin BubbleSort(elements)
for all item of elements
if elements[i] > elements[i+1]
swapFunction(elements[i], elements[i+1])
end if
end for
return elements
end BubbleSortJava Implementation for Bubble Sort
We have talked a lot about sorting through BubbleSort. Now Let’s try some practical java example to test our theory.
Below example program represents the code to perform bubble sorting of any list in Java. It has two main methods bubbleSort and printElements. The latter simply prints the array or list and the bubbleSort method has the actual program logic for bubble sort.
Similar to the pseudocode, it has two loops for iteration and whenever applicable the swapping of elements is happening. The outer loop loops through the entire array multiple times and inner loop loops through each element of the array.
Let’s see the code:
package com.main;
public class BubbleSort {
void bubbleSort(int elements[]) {
int l = elements.length;
for (int i = 0; i < l - 1; i++) {
for (int j = 0; j < l - i - 1; j++) {
if (elements[j] > elements[j + 1]) {
int temp = elements[j];
elements[j] = elements[j + 1];
elements[j + 1] = temp;
}
}
}
}
void printElements(int elements[]) {
int n = elements.length;
for (int i = 0; i < n; ++i) {
System.out.print(elements[i] + " , ");
}
System.out.println();
}
public static void main(String args[]) {
BubbleSort bs = new BubbleSort();
int elements[] = { 5, 2, 3, 6, 1, 4, 8 };
System.out.println("Actual List of Elements: ");
bs.printElements(elements);
bs.bubbleSort(elements);
System.out.println("Sorted List of Elements: ");
bs.printElements(elements);
}
}Output:
Actual list of elements 5 , 2 , 3 , 6 , 1 , 4 , 8 , Sorted list of elements 1 , 2 , 3 , 4 , 5 , 6 , 8 ,
Key Points for Java Bubble Sort
Here are some important key points related to Bubble sorting:
| Key | Description |
|---|---|
| Best Case Time Complexity | O(n). The Best case is considered when array is completely sorted in correct order. |
| Worst and Average Case Time Complexity | O(n*n). The Worst case is considered when the array or list is completely reverse sorted. |
| Boundary Cases | The minimum time of Bubble sort occurs if elements are already in correct order. |
| Auxiliary Space | O(1) |
| Sorting In Place | YES |
| Stable | YES |
Let’s see the implementation / program code for Bubble Sort in other languages:
Example: Implementation in C / C++
// C program for implementation of Bubble sort
#include <stdio.h>
void swapFunc(int *ap, int *bp)
{
int temp = *ap;
*ap = *bp;
*bp = temp;
}
void bubbleSort(int elements[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)
// Last i elements are already in place
for (j = 0; j < n-i-1; j++)
if (elements[j] > elements[j+1])
swapFunc(&elements[j], &elements[j+1]);
}
void printArray(int elements[], int n)
{
int i;
for (i=0; i < n; i++){
printf("%d ", elements[i]);
printf(","); }
}
// Main function
int main()
{
int elements[] = {5, 2, 3, 6, 1, 4, 8};
int n = sizeof(elements)/sizeof(elements[0]);
printf("Actual list of elements: \n");
printArray(elements, n);
bubbleSort(elements, n);
printf("\nSorted list of elements: \n");
printArray(elements, n);
return 0;
}Output :
Actual list of elements: 5 ,2 ,3 ,6 ,1 ,4 ,8 , Sorted list of elements: 1 ,2 ,3 ,4 ,5 ,6 ,8 ,
Example: Implementation in Python
# Python program for implementation of Bubble Sort
def bubbleSort(elements):
l = len(elements)
# Traverse through all elements
for i in range(l):
# Last i elements are already in place
for j in range(0, l-i-1):
# traverse the array from 0 to l-i-1
# Swap if the element is greater than the next element
if elements[j] > elements[j+1] :
elements[j], elements[j+1] = elements[j+1], elements[j]
# Main code to test the bubble sort
elements = [5, 2, 3, 6, 1, 4, 8]
print ("Actual list of elements is:")
for i in range(len(elements)):
print ("%d" %elements[i]),
bubbleSort(elements)
print ("\nSorted list of elements is:")
for i in range(len(elements)):
print ("%d" %elements[i]),Output :
Actual list of elements is: 5 2 3 6 1 4 8 Sorted list of elements is: 1 2 3 4 5 6 8
Example: Implementation in C# / C Sharp
// C# program for implementation of Bubble Sort
// using System;
class Test
{
static void bubbleSort(int []elements)
{
int l = elements.Length;
for (int i = 0; i < l - 1; i++)
for (int j = 0; j < l - i - 1; j++)
if (elements[j] > elements[j + 1])
{
// swap the elements
int temp = elements[j];
elements[j] = elements[j + 1];
elements[j + 1] = temp;
}
}
/* Prints the elements */
static void printArray(int []elements)
{
int l = elements.Length;
for (int i = 0; i < l; ++i)
Console.Write(elements[i] + " ");
Console.WriteLine();
}
// Main method
public static void Main()
{
int []elements = {5, 2, 3, 6, 1, 4, 8};
Console.WriteLine("Actual list of elements is :");
printArray(elements);
bubbleSort(elements);
Console.WriteLine("Sorted list of elements is :");
printArray(elements);
}
}
Output :
Actual list of elements is : 5 2 3 6 1 4 8 Sorted list of elements is : 1 2 3 4 5 6 8
Example: Implementation of Bubble Sort in Php
// PHP program for implementation of Bubble Sort
function bubbleSort(&$elements)
{
$l = sizeof($elements);
// Traverse through all elements
for($i = 0; $i < $l; $i++)
{
// Last i elements are already in place
for ($j = 0; $j < $l - $i - 1; $j++)
{
// traverse the array from 0 to n-i-1
// Swap if the element is greater than the next element
if ($elements[$j] > $elements[$j+1])
{
$temp = $elements[$j];
$elements[$j] = $elements[$j+1];
$elements[$j+1] = $temp;
}
}
}
}
$elements = array(5, 2, 3, 6, 1, 4, 8);
$l = sizeof($elements);
echo "Actual list of elements is : \n";
for ($i = 0; $i < $l; $i++)
echo $elements[$i]." ";
bubbleSort($elements);
echo "\nSorted list of elements is : \n";
for ($i = 0; $i < $l; $i++)
echo $elements[$i]." ";
?>
Output :
Actual list of elements is : 5 2 3 6 1 4 8 Sorted list of elements is : 1 2 3 4 5 6 8
Conclusion
Java Bubble sort is one of the simplest but high-cost algorithm. The process is simple- the adjacent elements are compared and sorted. However, this simple process requires so many steps to sort the element.
The complete code examples can be found in Github.
If you have any query / suggestion / feedback, please post the same into below comment box. You can also connect directly with me through social media icons placed on top of this page.
Thanks a lot for reading this article.
Happy Reading!!!!
