This tutorial shows how to write Bubble sort program in Java. Bubble sort is considered the simplest sorting algorithm out of the three simple sort algorithms, other two being Selection sort and Insertion sort, that work by comparing and swapping elements in each pass. Since there are a large number of comparisons and swaps Bubble sort is also considered the slowest sorting algorithm.
Bubble sort algorithm
Bubble sort works as follows-
You start from the left end and compare the first two elements (i.e. element at index 0 and index 1). If element on the left is greater than the element on right ( element at 0 > element at 1) you swap those two.
Move to next index and compare the two adjacent elements (i.e. element at index 1 and index 2). Again if element on the left is greater than the element on right you swap them.
This process is repeated until you reach the rightmost element. This is the first pass of the bubble sort and by the end of the first pass you have the greatest element at the rightmost end. In this sorting technique greatest elements bubble up to the higher indices of the array thus the name bubble sort.
In the next pass you start again from the first two elements (i.e. element at index 0 and index 1) and do the same comparing and swapping. Only difference is that in this pass iteration will be done for (N – 1) elements as element at the rightmost end is already at its sorted position.
For example if you have an array [6, 3, 10, 7, 1] then the first pass can be depicted as follows.
In the first iteration first two elements (6 and 3) are compared, since 6 is greater than 3 so elements are swapped. Same way in the next iteration 6 and 10 are compared and so on. By the end of the first pass greatest element in the array (10) bubbles up to the top of the array.
In the next pass only (N – 1) elements are considered thus the part of the array used is [3, 6, 7, 1].
Bubble Sort Java program
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {61, 34, 10, 0, 15, 112, 53, 78, 39, 45};
System.out.println("Original Array " + Arrays.toString(arr));
int[] sortedArr = bubbleSort(arr);
System.out.println("Sorted Array " + Arrays.toString(sortedArr));
}
private static int[] bubbleSort(int[] arr){
int n = arr.length;
for(int i = 0; i < n; i++){
for(int j = 0; j < (n - i - 1); j++){
if(arr[j] > arr[j+1]){
swapElements(j, arr);
}
}
}
return arr;
}
private static void swapElements(int index, int[] arr){
int temp = arr[index];
arr[index] = arr[index+1];
arr[index+1] = temp;
}
}
Output
Original Array [61, 34, 10, 0, 15, 112, 53, 78, 39, 45] Sorted Array [0, 10, 15, 34, 39, 45, 53, 61, 78, 112]
Bubble sort space and time complexity
Time complexity of bubble sort is O(n2).
No extra space is required so the space complexity of bubble sort is O(1).
That's all for the topic Bubble Sort Java Program. If something is missing or you have something to share about the topic please write a comment.
You may also like
No comments:
Post a Comment