Java Sorting is one of the many aspects of java interview questions. In this post, we will see java bubble sort example and write a program for bubble sort.
Bubble sort is also known as the exchange sort. It is the simplest algorithm for sorting numbers.
Bubble Sort Algorithm
- In bubble sort, the array of integers is traversed from index 0 to length-1.
- The value at 0th position is compared with the value at 1st position and if the later is small, it’s swapped.
- The comparison is moved from the 0th index to length-1 index so that after the first iteration, the last index has the biggest value.
- The same process is repeated again from 0th to length-1 index. After (length-1) iteration, the array is sorted.
- In worst-case, the complexity of bubble sort is O(n2) and in best-case, the complexity of bubble sort is Ω(n).
Bubble Sort in Java
Here is the implementation of Bubble Sort in Java program.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
import java.util.Arrays; public class BubbleSort { public static void main(String args[]) { int arr[] = { 5,4,3,2,1 }; int arr1[] = { 1,2,3,4,5 }; System.out.println("Array after sorting in ascending order:"+Arrays.toString(bubbleSortAscending(arr))); System.out.println("Array after sorting in descending order:"+Arrays.toString(bubbleSortDescending(arr1))); } public static int[] bubbleSortAscending(int[] arr){ int temp; for(int i=0; i < arr.length-1; i++){ for(int j=1; j < arr.length-i; j++){ if(arr[j-1] > arr[j]){ temp=arr[j-1]; arr[j-1] = arr[j]; arr[j] = temp; } } //check that last index has highest value in first loop, // second last index has second last highest value and so on System.out.println("Array after "+(i+1)+"th iteration:"+Arrays.toString(arr)); } return arr; } public static int[] bubbleSortDescending(int[] arr){ int temp; for(int i=0; i < arr.length-1; i++){ for(int j=1; j < arr.length-i; j++){ if(arr[j-1] < arr[j]){ temp=arr[j-1]; arr[j-1] = arr[j]; arr[j] = temp; } } //check that last index has highest value in first loop, // second last index has second last highest value and so on System.out.println("Array after "+(i+1)+"th iteration:"+Arrays.toString(arr)); } return arr; } } |
The above program is for sorting in ascending as well as descending order using bubble sort algorithm.
Output of the above program is:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
<span style="color: #008000;"><strong><code> Array after 1th iteration:[4, 3, 2, 1, 5] Array after 2th iteration:[3, 2, 1, 4, 5] Array after 3th iteration:[2, 1, 3, 4, 5] Array after 4th iteration:[1, 2, 3, 4, 5] Array after sorting in ascending order:[1, 2, 3, 4, 5] Array after 1th iteration:[2, 3, 4, 5, 1] Array after 2th iteration:[3, 4, 5, 2, 1] Array after 3th iteration:[4, 5, 3, 2, 1] Array after 4th iteration:[5, 4, 3, 2, 1] Array after sorting in descending order:[5, 4, 3, 2, 1] </code></strong></span> |
As we can see that in every iteration, the last index is getting sorted and it takes (array length – 1) iterations for sorting.
You can checkout complete example and more sorting algorithm implementations at our GitHub Repository.