You're a programmer, right? But do you rally think like programmers (or computer scientists) do?
When going for job interviews, you're likely to meet data structure and algorithm questions. This helps companies make sure they hire a systematic problem solver developer.
In this shot, I want you to learn more about one of the simplest sorting algorithms out there: bubble sort. How it works and how do we implement it with Java language.
The bubble sort in a nutshell
There we are: what is bubble sort?
Bubble sort is one type of sorting algorithms, and the simplest one, which is used to repeatedly compare adjacent items in a list and exchange them if they are in wrong order.
Let consider a list that need to be sorted in ascending order. To do this with bubble sort, we will start by comparing the first item of the list with the second one, if the first item is greater than the second, we swap both items, and then move on to compare the second and the third items, and so on. So, for a given list of size n
, we need to repeat this process n - 1
times.
Note:
- bubble sort is also called comparison alogorithm
- In real life, we can observe bubble sort when people in a queue wanting to be standing in a high wise sorted manner swap their positions among themselves until everyone is standing based on increasing order of heights
Let's visualize an example of bubble sort so that you get it very well.
Bubble sort in practice
Here, I'll explain with an example how the bubble sort works, then after we will implement the algorithm in Java.
Let's consider this list of integer values: 19, 1, 9, 3, 10, 13
. We want it to be sorted in ascending order.
We can now proceed with the comparison. You can notice that I've added indexes above each item of the list.
First iteration
- We start with the first and second item:
19 > 1
is true, so we need to swap both items.
Our list looks now like this:
- Next, we compare the second item with the third one:
19 > 9
is true, again we need to swap.
The new list is formed as follows:
- We proceed with the third and fourth items:
19 > 3
is true, we swap as before.
Again, our list is arranged like this:
- Let's continue the comparison with the fourth and the fifth items:
19 > 10
is true, once more we swap.
After swapping, the list is now as follows
- We proceed with the fifth item and the last one:
19 > 13
is true, we need to swap.
Thus, after swapping item 5 and item 6, the list becomes:
This is the end of the first iteration. Notice how the largest item (19
) is at the last position. 10
and 13
are also at their position.
Second iteration
We will be doing the same thing as in the first iteration.
- We proceed with the first and the second items:
1 > 9
is false, so no swapping.
- Next, we proceed with
9
and3
:9 > 3
is true, we swap.
After swapping, the list is now like this:
Every item is in its right position. This marks the end of the process.
Note: If the list was not yet sorted as expected, we could continue with the third, nth processes until we get a fully sorted list.
Bubble sort: Pseudocode
It's always a good practice to use pseudocode before actual implementation. This is one for the bubble sort.
function bubbleSort(arr)
Set isSwapped to true
WHILE isSwapped = true
Reset isSwapped to false
FOR each item in the arr
IF current item > next item
swap items
Reset isSwapped to true
ENDIF
ENDFOR
ENDWHILE
RETURN arr
Bubble sort: Java implementation
Now is the time to implement the algorithm. We are using Java here. If you want a JavaScript implementation, use this link.
We create two classes:
-
BubbleSort.java
for the implementation of the logic -
Main.java
to test the implementation
BubbleSort.java
Let's create a method called sort()
and implement the first iteration.
public class BubbleSort {
public void sort(int[] list) {
for (int i = 0; i < list.length - 1; i++) {
if(list[i] > list[i + 1]) {
// swap is true
int temp = list[i];
list[i] = list[i + 1];
list[i + 1] = temp;
}
}
}
}
Our method is not that complicated. We're going through the list of integers by comparing adjacent items to see if they need to be swapped. If so, we do swap them. Look how we've implemented our swapping system:
- first, we keep the left item in temporary variable,
temp
- next, we assign the value of the right item to the left one
- last, the right item is assigned
temp
To make our code cleaner and more readable, let's move the swap logic into a method called swap()
.
private void swap(int[] list, int curr_index) {
int temp = list[curr_index];
list[curr_index] = list[curr_index + 1];
list[curr_index + 1] = temp;
}
Our is working pretty fine, but only for one iteration, which is not enough to sort the list as expected.
Let's modify the code so that it can loop over and over until we get a fully sorted list.
public class BubbleSort {
public void sort(int[] list) {
boolean isSwapped = true;
while (isSwapped) {
isSwapped = false;
for (int i = 0; i < list.length - 1; i++) {
if(list[i] > list[i + 1]) {
isSwapped = true;
swap(list[i], list[i + 1]);
}
}
}
}
private void swap(int left_item, int right_item) {
int temp = left_item;
left_item = right_item;
right_item = temp;
}
}
What did we do here? We've created a boolean variable, isSwapped
and initialized to true
so that we can use it in a while
loop. Inside the while
loop, we first assume that we want need swapping, so we set isSwapped
to false
. If we end up swapping, we reset it back to true
.
We can now test our implementation.
Main.java
public class BubbleSort {
public void sort(int[] list) {
boolean isSwapped = true;
while (isSwapped) {
isSwapped = false;
for (int i = 0; i < list.length - 1; i++) {
if(list[i] > list[i + 1]) {
swap(list, i);
isSwapped = true;
}
}
}
}
private void swap(int[] list, int curr_index) {
int temp = list[curr_index];
list[curr_index] = list[curr_index + 1];
list[curr_index + 1] = temp;
}
}
Congratulations! You've been able to implement Bubble sort algorithm in Java.
One more thing for your information: complexity of the algorithm
Complexity analysis
To end our journey, let me say just one word about the performance of this algorithm.
Bubble sort is a very simple sorting algorithm and also the very slow one. For this reason, you'll almost never find or use it in the real world. In fact, it is mostly used for educational purposes.
- Worst Case Time Complexity, aka Big-O: $O(n^2)$
- Best Case Time Complexity, aka Big-omega: $O(n)$
- Average Time Complexity, aka Big-theta: $O(n^2)$
- Space Complexity: $O(1)$
Happy coding!
Top comments (0)