Bubble Sort is the first sorting algorithm I learned during my college day, and after so many years it's the one I remember by heart. It's kind of weird that one of the most popular sorting algorithm is also one of the worst performing sorting algorithm. Bubble sort's average case performance is in O(n^2), which means as the size array grows, the time it take to sort that array increases quadratic. Due to this reason, bubble sort is not used in production code, instead quick sort and merge sort are preferred over it. In fact, Java's own Arrays.sort() method, which is the easiest way to sort an array in Java also uses two pivot quicksort to sort primitive array and stable mergesort algorithm to sort object arrays. The reason or slow performance of this algorithm is excessive comparison and swapping, since it compare each element of array to another and swaps if it is on right side. Due to quadratic performance, bubble sort is best suited for small, almost sorted list e.g. {1, 2, 4, 3, 5} , where it just need to do one swapping. Ironically, best case performance of bubble sort, which is O(n) beats quicksort's best case performance of O(NlogN). Someone may argue that why teaching an algorithm which that poor performance, why not teach insertion or selection sort which is as easy as bubble sort, and performs better. IMHO, easiness of algorithm depends upon programmer as much as on algorithm itself. Many programmer will find insertion sort easier than bubble sort but again there will be a lot many who will find bubble sort easier to remember, including myself. This is true, despite many of them have used insertion sort unknowingly in real life, e.g. sorting playing cards in hand. Another reason for learning this sorting algorithm is for comparative analysis, how you improve algorithms, how you come up with different algorithms for same problems. In short, despite of all its shortcomings, bubble sort is still the most popular algorithm. In this tutorial, we will learn how bubble sort works, complexity and performance of bubble sort algorithm, implementation and source code in Java and a step by step example of bubble sort.
How Bubble Sort Algorithm works
If you are the one who focus on names, then you might have got an idea how bubble sort works. Just like a bubble comes up from water, in bubble sort smallest or largest number, depending upon whether you are sorting array on ascending or descending order, bubbles up towards start or end of the array. We need at least N pass to sort the array completely and at the end of each pass one elements are sorted in its proper position. You can take first element from array, and start comparing it with other element, swapping where it's lesser than the number you are comparing. You can start this comparison from start or from end, as we have compared elements from end in our bubble sort example. It is said that a picture is worth more than a thousand word and it's particularly true in case of understanding sorting algorithm. Let' see an step by step example to sort array using bubble sort, as I said after each pass largest number is sorted.
In this array, we start from index 0, which is 5 and starts comparing elements from start to end. So first element we compare 5 is 1, and since 5 is greater than 1 we swap them ( because ascending order sorted array will have larger number towards end). Next we compare 5 to 6, here no swapping because 6 is greater than 5 and it's on higher index than 5. Now we compare 6 to 2, again we need swapping to move 6 towards end. At the end of this pass 6 reaches (bubbles up) at the top of the array. In next iteration 5 will be sorted on its position and after n iteration all elements will be sorted. Since we compare each element with another, we need two for loops and that result in complexity of O(n^2).
FlowChart of Bubble Sort Algorithm
Another cool way to understand an algorithm is to draw it's flowchart. It will walk through each iteration in loop and how decisions are made during algorithm execution. Here is flowchart of our bubble sort algorithm, which complements our implementation of this sorting algorithm.
Here we have integer array {9, 7, 3, 6, 2} and start with four variable i, j, temp and array length which is stored in variable n. We have two for loop, outer loop runs from 1 to n-1. Our inner loop runs from n-1 to i. Many programmer make mistake here, if you start outer loop with second element than make sure to use j>=i condition on inner loop, or if you start with first element e.g. i=0, make sure you use j>i to avoid ArrayIndexOutOfBound exception. Now we compare each element and swap them to move smaller element towards front of array. As I said depending upon your navigation direction either largest element will be sorted at highest index in first pass or smallest element will be placed in lowest index. In this case, after first pass, smallest number will be sorted. This loop runs until j>=i after than it finishes and i becomes i + 1. This whole process repeats until outer loop is finished and that time your array is sorted. In flowchart, a diamond box is used for decision making, which is equivalent of if-else statement in code. You can see here decision box is inside inner loop, which means we do N comparison in each iteration, totals to NxN comparisons.
Complexity and Performance of Bubble Sort Algorithm
As I said before compared to other sorting algorithm like quicksort, merge sort or shell sort, bubble sort performs poorly. These algorithm has average case complexity of O(NLogN), while average case complexity of bubble sort O(n^2). Ironically in best case bubble sort do better than quicksort with O(n) performance. Bubble sort is three times slower than quicksort or mergesort even for n = 100 but it's easier to implement and remember. here is the summary of bubble sort performance and complexity :
Bubble sort Worst case performance O(n^2)
Bubble sort Best case performance O(n)
Bubble sort Average case performance O(n^2)
You can further explore insertion sort and selection sort, which also does sorting in similar time complexity. By the you can not only sort the array using bubble sort but ArrayList or any other collection class as well. Though you should really use Arrays.sort() or Collections.sort() for those purpose.
Bubble Sort Implementation in Java
here is the Java program to implement bubble sort algorithm using Java programming language. Don't surprise with import of java.util.Array, we have not used it's sort method here, instead it is used to print arrays in readable format. I have created a swap function to swap numbers and improve readability of code, if you don't like you can in-line the code in the swap method inside if statement of inner loop. Though I have used main method for testing, as it demonstrate better, I would suggest you to write some unit test case for your bubble sort implementation. If you don't know how to do that, you can see this JUnit tutorial.
import java.util.Arrays;
/**
* Java program to implement bubble sort algorithm and sort integer array using
* that method.
*
* @author Javin Paul
*/
public class BubbleSort{
public static void main(String args[]) {
bubbleSort(new int[] { 20, 12, 45, 19, 91, 55 });
bubbleSort(new int[] { -1, 0, 1 });
bubbleSort(new int[] { -3, -9, -2, -1 });
}
/*
* This method sort the integer array using bubble sort algorithm
*/
public static void bubbleSort(int[] numbers) {
System.out.printf("Unsorted array in Java :%s %n", Arrays.toString(numbers));
for (int i = 0; i < numbers.length; i++) {
for (int j = numbers.length -1; j > i; j--) {
if (numbers[j] < numbers[j - 1]) {
swap(numbers, j, j-1);
}
}
}
System.out.printf("Sorted Array using Bubble sort algorithm :%s %n",
Arrays.toString(numbers));
}
/*
* Utility method to swap two numbers in array
*/
public static void swap(int[] array, int from, int to){
int temp = array[from];
array[from] = array[to];
array[to] = temp;
}
}
Output
Unsorted array in Java : [20, 12, 45, 19, 91, 55]
Sorted Array using Bubble sort algorithm : [12, 19, 20, 45, 55, 91]
Unsorted array in Java : [-1, 0, 1]
Sorted Array using Bubble sort algorithm : [-1, 0, 1]
Unsorted array in Java : [-3, -9, -2, -1]
Sorted Array using Bubble sort algorithm : [-9, -3, -2, -1]
How to improve Bubble Sort Algorithm
In interview one of the popular follow-up question is how do you improve a particular algorithm, and Bubble Sort is no different than that. If you wrote bubble sort like the one we have shown here, interviewer will definitely going to ask about how do you improve your bubble sort method. In order to improve any algorithm, you must understand how each step of that algorithm works, then only you will be able to spot any deficiency in code. If you follow the tutorial, you will find that array is sorted by moving elements to their correct position. In worst case situation if array is reverse sorted then we need to move every element, this will require n-1 passes, n-1 comparison in each pass and n-1 exchanges, but how about best case if array is already sorted, our existing bubble sort method is still going to take n-1 pass, same number of comparison but no exchange. If you observe carefully, you will find that after one pass through the array, the largest element will moved to the end of the array, but many other elements also moved toward their correct positions, as bubbles move toward the water’s surface. By leveraging this property, you can deduce that during a pass, if no pair of consecutive entries is out of order, then the array is sorted. Our current algorithm is not taking advantage of this property. If we track exchanges then we can decide whether additional iteration over array is needed or not. Here is an improved version of Bubble Sort algorithm, which will only take 1 iteration and n-1 comparison in best case, when array is already sorted. This will also improve Bubble sort's average case performance, as compared to our existing method which will always take N - 1 passes.
/*
* An improved version of Bubble Sort algorithm, which will only do
* 1 pass and n-1 comparison if array is already sorted.
*/
public static void bubbleSortImproved(int[] number) {
boolean swapped = true;
int last = number.length - 2;
// only continue if swapping of number has occurred
while (swapped) {
swapped = false;
for (int i = 0; i <= last; i++) {
if (number[i] > number[i + 1]) {
// pair is out of order, swap them
swap(number, i, i + 1);
swapped = true; // swapping occurred
}
}
// after each pass largest element moved to end of array
last--;
}
}
Now let's test this method for two input, one in which array is sorted (best case) and other on which only one pair is out of order. If we pass int array {10, 20, 30, 40, 50, 60} to this method, initially will go inside while loop and make swapped=false. Then it will go inside for loop. when i =0 it will compare number[i] to number[i+1] i.e. 10 to 20 and check if 10 > 20, since it's not it will not go inside if block and no swapping will be occurred. When i=1, it will compare 20 > 30 again no swapping, next when i =2 30> 40 which is false so no exchange again, next i =3 so 40> 50, which is again false, so no swapping. Now last pair comparison i=4, it will compare 50 > 60 again this is false, so control will not go inside if block and no exchange will be made. Because of that swapped will remain false and control will not go inside while loop again. So you know that your array is sorted just after one pass.
Now consider another example, where just one pair is out of order, let's say String array names = {"Ada", "C++", "Lisp", "Java", "Scala"}, here only one pair is out of order e.g. "Lisp" should come after "Java". Let's see how our improved bubble sort algorithm work here. In first pass, comparison will continue without exchange until we compare "Lisp" to "Java", here "Lisp".compareTo("Java") > 0 will become true and swapping will occur, which means Java will go to the Lisp place, and Lisp will take Java's place. this will make boolean variable swapped=true, Now in last comparison on this pass, we compare "Lisp" to "Scala" and again no exchange. Now we will reduce last index by 1 because Scala is sorted at last position and will not participate further. But now swapped variable is true, so control will again go inside while loop, and for loop but this time no exchanged will be made so it will not take another pass. Our array is now sorted in just two pass compared to N-1 pass of earlier implementation. This bubble sort implementation is much better and even perform better than Selection sort algorithm in average case because, now sorting is not proportional to total number of elements but only with number of pairs which are out-of-order.
By the way to sort String array using Bubble Sort, you need to overload BubbleSortImproved() method to accept String[] and also need to use compareTo() method to compare two String object lexicographically. Here is Java program to sort String array using Bubble Sort :
import java.util.Arrays;
class BubbleSortImproved {
public static void main(String args[]) {
String[] test = {"Ada", "C++", "Lisp", "Java", "Scala"};
System.out.println("Before Sorting : " + Arrays.toString(test));
bubbleSortImproved(test);
System.out.println("After Sorting : " + Arrays.toString(test));
}
/*
* An improved implementation of Bubble Sort algorithm, which will only do
* 1 pass and n-1 comparison if array is already sorted.
*/
public static void bubbleSortImproved(String[] names) {
boolean swapped = true;
int last = names.length - 2;
// only continue if swapping of number has occurred
while (swapped) {
swapped = false;
for (int i = 0; i <= last; i++) {
if (names[i].compareTo(names[i + 1]) > 0) {
// pair is out of order, swap them
swap(names, i, i + 1);
swapped = true; // swapping occurred
}
}
// after each pass largest element moved to end of array
last--;
}
}
public static void swap(String[] names, int fromIdx, int toIdx) {
String temp = names[fromIdx]; // exchange
names[fromIdx] = names[toIdx];
names[toIdx] = temp;
}
}
Output:
Before Sorting : [Ada, C++, Lisp, Java, Scala]
After Sorting : [Ada, C++, Java, Lisp, Scala]
Which one is better Selection Sort vs Bubble Sort?
Though both Selection Sort and Bubble sort has complexity of O(n^2) in worst case. On average, we expect the bubble sort to perform better than Selection sort, because bubble sort will finish sorting sooner than the selection sort due to more data movements for the same number of comparisons, because we compare elements in pair on Bubble Sort. If we use our improved implementation Bubble Sort then a boolean test to not enter on while loop when array gets sorted will also help. As I said, The worst case of the bubble sort happens when the original array is in descending order, while in best case, if the original array is already sorted, the bubble sort will perform only one pass whereas the selection sort will perform N - 1 passes. Given this, I think on average Bubble sort is better than Selection sort.
That's all about Bubble Sort in Java. We have learned how bubble sort algorithm works and how do you implement it in Java. As I said, it is one of the simplest sorting algorithm and very easy to remember, but also it doesn't have any practical use apart from academics and in data structure and algorithm training classes. It's worst case performance is quadratic which means it not suitable for large array or list. If you have to use bubble sort, it's best suited for small, already sorted array in which case it has to very few swapping and it's performance is in O(n). If you love algorithms, you can see this problem of finding cycle on linked list.
Tidak ada komentar:
Posting Komentar