Optimized Bubble Sort in Java
In this post, we will learn how to optimize bubble sort algorithm. This is very basic interview question in many product based companies for freshers and 0-2 experience.Of course, Bubble Sort is one of the slowest algorithm but still we can optimize it for better performance and this is only for smaller set of input.
If you do not know bubble sort algorithm and how it works then please go through below article for better understating of optimization.
More on How to write a Program on Bubble Sort
Areas to Optimize:
Where can we optimize it. Following are areas to think about optimization.1) Consider example array : 9 5 7 3 1
We will have to iterate 5 times from index 0 to 4.
Iteration 1: when we run the inner loop 1st time then largest value will be moved to the right side of it that is at array n-1 position. Loop from index 0 to n-1
5 7 3 1 9
Iteration 2: In 2nd iteration of inner loop, 2nd largest value will be moved to second position from right side of array that is at n-2 position. Loop from 0 to n-1. Observe here actually, value at n-1 position value is already sorted and having largest value from above step. Here if we can run the loop till n-2 is a option for optimize it.
5 3 1 7 9
Iteration 3: For 3rd iteration of inner loop which is again loop from index 0 to n-1. After loop completion, 3rd largest value is at n-3 position of the array. But loop is from 0 to n-1. Here also loop is not requried till n-1 because n-1, n-2 elements are already sorted. and so on.....for reamining iterations.
3 1 5 7 9
2) If an given array is already sorted.
Eg. 1 3 5 7 9
Consider above array, which is already sorted. But using normal bubble sorting algorithm, we will have to go through loop from index 0 to 4 for 5 times because array length is 5.
3) Given array is not sorted, but it may become sorted at any point of time in inner loop.
Eg. 9 1 3 5 7
We will have to iterate 5 times from index 0 to 4.
Iteration 1: 1 3 5 7 9 --> swap is done.
Iteration 2: Seems array it is sorted. But, how to identify it is sorted is to iterate the loop from index 0 to 4, mark the flag as true if any swap is done using boolean variable.
Here it has become in second iteration.
If we do these three then Bubble sort is otimized.
If you see any area to improment in this sorting, Please post in comment.
Optimized Algorithm:
n = length(inputArrayValues) isSwapped = true;
iterateCount = 0;
repeat
isSwapped = false
for i = 1 to n-1-iterateCount inclusive do
if inputArrayValues[i-1] > inputArrayValues[i] then
swap(inputArrayValues[i-1], inputArrayValues[i])
isSwapped = true
end if
end for
until not isSwappedOptimized Bubble Sort Program:
package com.adeepdrive.sorting;
public class OptimizedBubbleSort {
public static void main(String[] Args) {
int[] inputArrayValues = { 9, 5, 7, 3, 1 };
System.out.print("input array before sorting : ");
printInputArray(inputArrayValues);
boolean isSwapped = true;
int iterateCount = 0;
while (isSwapped) {
isSwapped = false;
for (int i = 0; i < inputArrayValues.length - 1 - iterateCount; i++) {
if (inputArrayValues[i] > inputArrayValues[i + 1]) {
int temp = inputArrayValues[i];
inputArrayValues[i] = inputArrayValues[i + 1];
inputArrayValues[i + 1] = temp;
isSwapped = true;
}
}
iterateCount++;
System.out.print("\nIterate " + iterateCount + " : ");
printInputArray(inputArrayValues);
}
System.out.print("\ninput array after sorting : ");
printInputArray(inputArrayValues);
}
public static void printInputArray(int[] values) {
for (int value : values) {
System.out.print(value + " ");
}
}
}
Output 1 for input 1:
input array before sorting : 9 5 7 3 1Iterate 1 : 5 7 3 1 9
Iterate 2 : 5 3 1 7 9
Iterate 3 : 3 1 5 7 9
Iterate 4 : 1 3 5 7 9
Iterate 5 : 1 3 5 7 9
input array after sorting : 1 3 5 7 9
Pass input array : int[] inputArrayValues = { 9, 1, 3, 5, 7 };
Output 2 for input 2:
input array before sorting : 9 1 3 5 7
Iterate 0 : 1 3 5 7 9
Iterate 1 : 1 3 5 7 9
input array after sorting : 1 3 5 7 9
See the differences between output 1 and output 2. If the array becomes sorted then it will exit from loop.
This is how we optimize.
Please leave your questions in comments section.
0 Comments