Bubble Sort Java Algorithm:-
- Key Point is: Take a pair from the collection of item and compare. If they have wrong order swap them.
- Flow:
- Consider a sequence 4, 2, 3, 1
- Sort in increasing order
Java Bubble Sort Process:-
< Outer Loop>
In first loop < Sequence is 4, 2, 3, 1 >
< Inner Loop >
As par key point compare 4 and 2 as 4 > 2, swap the number
Now sequence is 2, 4, 3, 1
Take 4 and 3, 4 > 3, swap the number
Now sequence is 2, 3, 4, 1
Take 4 and 1, 4 > 1, swap the number
Now sequence is 2, 3, 1, 4
< Inner Loop End>
In second Loop < Sequence is 2, 3, 4, 1 >
< Inner Loop >
Take 2 and 3 as 2 > 3, don’t swap
Now sequence is 2, 3, 1, 4
Take 3 and 1, 3 > 1, swap the number
Now sequence is 2, 1, 3, 4
Take 3 and 4, 3 > 4, don’t swap
Now sequence is 2, 1, 3, 4
< Inner Loop End>
In Third Loop < Sequence is 2, 1, 3, 4 >
< Inner Loop >
Take 2 and 1 as 2 > 1, swap the number
Now sequence is 1, 2, 3, 4
Take 2 and 3, 2 > 3, don’t swap
Now sequence is 1, 2, 3, 4
Take 3 and 4, 3 > 4, don’t swap
Now sequence is 1, 2, 3, 4
< Inner Loop End>
In Fourth Loop < Sequence is 1, 2, 3, 4 >
< Inner Loop >
Take 1 and 2 as 2 > 1, don’t swap
Now sequence is 1, 2, 3, 4
Take 2 and 3, 2 > 3, don’t swap
Now sequence is 1, 2, 3, 4
Take 3 and 4, 3 > 4, don’t swap
Now sequence is 1, 2, 3, 4
< Inner Loop End>
< Outer Loop End >
Sorted list is
1, 2, 3, 4
From the above example we see the outer loop execute 4 times and inner loop 3 times.
So total number of execution on sequence is 4*3 = 12 to get sorted sequence.
So suppose we have n number, than total number of execution would be n*n-1.
Below is the implementation of the Bubble Sort for Increasing order as well as decreasing order.
Bubble Sort with ArrayList in Java Implementation:-
package one;
import java.util.ArrayList;
public class MyBubbleSort
{
public static void main(String[] args)
{
ArrayList<Integer> arrayList = new ArrayList<Integer>();
// Add the elements
arrayList.add(10);
arrayList.add(3);
arrayList.add(8);
arrayList.add(1);
arrayList.add(9);
arrayList.add(5);
arrayList.add(2);
arrayList.add(4);
arrayList.add(6);
arrayList.add(7);
arrayList.add(5);
// Display the list
System.out.print("List of Array is ");
for(Integer i : arrayList)
System.out.print(i + ", ");
// second parameter of bubbleSort function is true, means we will get sorted list
// in decreasing order
// To get sorted List in increasing order pass the second parameter as false
bubbleSort(arrayList, true);
System.out.print("\n\nSorted List of Array is ");
for(Integer i : arrayList)
System.out.print(i + ", ");
}
// Increasing Order
private static void bubbleSort(ArrayList<Integer> arrayList, boolean flag)
{
Integer tempInt;
if (flag)
{
bubbleSort(arrayList);
return;
}
for(int outerCount = 0; outerCount < arrayList.size() - 1; outerCount++)
{
for(int innerCount = 0; innerCount < (arrayList.size() - outerCount - 1) ; innerCount++)
{
if( arrayList.get(innerCount) >= arrayList.get(innerCount+1) )
{
tempInt = arrayList.get(innerCount);
arrayList.set(innerCount, arrayList.get(innerCount+1));
arrayList.set(innerCount+1, tempInt);
}
}
}
}
// Decreasing Order
private static void bubbleSort(ArrayList<Integer> arrayList)
{
Integer tempInt;
for(int outerCount = 0; outerCount < arrayList.size() - 1; outerCount++)
{
for(int innerCount = 0; innerCount < (arrayList.size() - outerCount - 1) ; innerCount++)
{
if( arrayList.get(innerCount) <= arrayList.get(innerCount+1) )
{
tempInt = arrayList.get(innerCount);
arrayList.set(innerCount, arrayList.get(innerCount+1));
arrayList.set(innerCount+1, tempInt);
}
}
}
}
}
Output is:-
List of Array is 10, 3, 8, 1, 9, 5, 2, 4, 6, 7, 5,
Sorted List of Array is 10, 9, 8, 7, 6, 5, 5, 4, 3, 2, 1,
