**This Tutorial will Explain the Bubble Sort in Java along with Major Java Sorting Algorithm, Bubble Sort Implementation & Code Examples:**

A sorting algorithm can be defined as an algorithm or a procedure to put elements of a collection in a specific order. For instance, if you have a numeric collection like an ArrayList of integers, then you might want to arrange the elements of ArrayList in ascending or descending order.

Similarly, you might want to arrange strings of a string collection in alphabetical or lexicographical order. This is where the sorting algorithms in Java come into the picture.

What You Will Learn:

## Major Sorting Algorithms In Java

Sorting algorithms are usually evaluated depending on the time and space complexities. Java supports various sorting algorithms that are used to sort or arrange the collections or data structures.

The table below shows the major sorting algorithms supported in Java along with their best/ worst-case complexities.

Time complexity | ||||
---|---|---|---|---|

Sorting algorithm | Description | Best case | Worst case | Average case |

Bubble Sort | Compares the current element to adjacent elements repeatedly. At the end of each iteration, the heaviest element gets bubbled up at its proper place. | O(n) | O(n^2) | O(n^2) |

Insertion Sort | Inserts each element of the collection in its proper place. | O(n) | O(n^2) | O(n^2) |

Merge Sort | It follows the divide and conquer approach. Divides the collection into simpler sub-collections, sorts them and then merges everything | O(nlogn) | O(nlogn) | O(nlogn) |

Quick Sort | Most efficient and optimized sorting technique. Uses divide and conquer to sort the collection. | O(nlogn) | O(n^2) | O(nlogn) |

Selection Sort | Finds the smallest element in the collection and put it in its proper place at the end of every iteration | O(N^2) | O(N^2) | O(N^2) |

Radix Sort | Linear sorting algorithm. | O(nk) | O(nk) | O(nk) |

Heap Sort | Elements are sorted by building min heap or max heap. | O(nlogn) | O(nlogn) | O(nlogn) |

**Apart from the sorting techniques given in the above table, Java also supports the following sorting techniques:**

- Bucket Sort
- Counting Sort
- Shell Sort
- Comb Sort

But these techniques are used sparingly in practical applications, thus these techniques will not be part of this series.

**Let’s discuss the Bubble Sort Technique in Java.**

## Bubble Sort In Java

Bubble sort is the simplest of all sorting techniques in Java. This technique sorts the collection by repeatedly comparing two adjacent elements and swapping them if they are not in the desired order. Thus, at the end of the iteration, the heaviest element gets bubbled up to claim its rightful position.

If there are n elements in list A given by A[0],A[1],A[2],A[3],….A[n-1], then A[0] is compared to A[1], A[1] is compared to A[2] and so on. After comparing if the first element is greater than the second, then the two elements are swapped if they are not in order.

### Bubble Sort Algorithm

**The general algorithm for Bubble Sort Technique is given below:**

**Step 1:** For i = 0 to N-1 repeat Step 2

**Step 2:** For J = i + 1 to N – I repeat

**Step 3:** if A[J] > A[i]

Swap A[J] and A[i]

[End of Inner for loop]

[End if Outer for loop]

**Step 4:** Exit

Now let’s demonstrate the Bubble Sort Technique using an illustrative example.

We take an array of size 5 and illustrate the bubble sort algorithm.

### Sort An Array Using Bubble sort

**The following list is to be sorted.**

As you can see above, the array is entirely sorted.

**The above illustration can be summarized in tabular form as shown below:**

Pass | Unsorted list | comparison | Sorted list |
---|---|---|---|

1 | {11, 3, 6,15,4} | {11,3} | {3,11,6,15,4} |

{3,11,6,15,4} | {11,6} | {3,6,11,15,4} | |

{3,6,11,15,4} | {11,15} | {3,6,11,15,4} | |

{3,6,11,15,4} | {15,4} | {3,6,11,4,15} | |

2 | {3,6,11,4,15} | {3,6} | {3,6,11,4,15} |

{3,6,11,4,15} | {6,11} | {3,6,11,4,15} | |

{3,6,11,4,15} | {11,4} | {3,6,4,11,15} | |

3 | {3,6,4,11,15} | {3,6} | {3,6,4,11,15} |

{3,6,4,11,15} | {6,4} | {3,4,6,11,15} | |

{3,4,6,11,15} | SORTED |

As shown in the above example, the largest element bubbles up to its proper position with every iteration/pass. In general, when we reach N-1 (where N is a total number of elements in the list) passes; we will have the entire list sorted.

### Bubble Sort Code Example

The below program shows the Java implementation of the bubble sort algorithm. Here, we maintain an array of numbers and use two for loops to traverse through adjacent elements of the array. If two adjacent elements are not in order, then they are swapped.

import java.util.*; class Main{ // Driver method to test above public static void main(String args[]) { //declare an array of integers int intArray[] = {23,43,13,65,11,62,76,83,9,71,84,34,96,80}; //print original array System.out.println("Original array: " + Arrays.toString(intArray)); int n = intArray.length; //iterate over the array comparing adjacent elements for (int i = 0; i < n-1; i++) for (int j = 0; j < n-i-1; j++) //if elements not in order, swap them if (intArray[j] > intArray[j+1]) { int temp = intArray[j]; intArray[j] = intArray[j+1]; intArray[j+1] = temp; } //print the sorted array System.out.println("Sorted array: " + Arrays.toString(intArray)); } }

**Output:**

Original array: [23, 43, 13, 65, 11, 62, 76, 83, 9, 71, 84, 34, 96, 80]

Sorted array: [9, 11, 13, 23, 34, 43, 62, 65, 71, 76, 80, 83, 84, 96]

### Frequently Asked Questions

**Q #1) What are the Sorting Algorithms in Java?**

**Answer:** The sorting algorithm can be defined as an algorithm or procedure using which the elements in a collection can be ordered or arranged in a desired fashion.

**Given below are some of the sorting algorithms supported in Java:**

- Bubble Sort
- Insertion sort
- Selection sort
- Merge sort
- Quicksort
- Radix sort
- Heapsort

**Q #2) ****What is the best Sorting Algorithm in Java?**

**Answer:** Merge Sort is supposed to be the fastest sorting algorithm in Java. In fact, Java 7 has internally used merge sort to implement the Collections.sort () method. Quick Sort is also another best sorting algorithm.

**Q #3) ****What is Bubble sort in Java?**

**Answer:** Bubble sort is the simplest algorithm in Java. Bubble sort always compares two adjacent elements in the list and swaps them if they are not in the desired order. Thus, at the end of every iteration or pass, the heaviest element is bubbled up to its proper place.

**Q #4) ****Why is Bubble sort N ^{2}?**

**Answer: **For implementing bubble sort, we use two for loops.

**The total work done is measured by:**

Amount of work done by inner loop * total number of times the outer loop runs.

For a list of n elements, the inner loop works for O(n) for each iteration. The outer loop runs for O (n) iteration. Hence the total work done is O(n) *O(n) = O(n^{2})

**Q #15) ****What are the Advantages of Bubble sort?**

**Answer: Advantages of Bubble Sort are as follows:**

- Easy to code and understand.
- Few lines of code are required to implement the algorithm.
- The sorting is done in-place i.e. additional memory is not required and thus no memory overhead.
- The sorted data is immediately available for processing.

## Conclusion

So far, we discussed the Bubble Sort sorting algorithm in Java. We also explored the algorithm and detailed illustration of sorting an array using the Bubble Sort Technique. Then we implemented the Java program to the Bubble Sort.

**In the next tutorial, we will continue with the other sorting techniques in Java.**