If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
In this post, we will see how to implement Bubble sort in java. Bubble sort is also known as sinking sort.Bubble sort is a comparison based sorting algorithm and is very easy to implement.
Bubble sort algorithm:
Bubble sort works by iterating first element to last element, comparing two adjacent elements and swapping them if they are not in correct order. Each iteration places next larger value to its correct place.
Why bubble sort is called bubble sort or sinking sort(From wikipedia):
Bubble sort can be done in ascending order or descending order.
Reason for being called Sinking sort:
The larger values might be regarded as heavier and therefore be seen to progressively sink to the bottom of the list
Reason for being called Bubble sort:
The smaller values might be regarded as lighter and therefore be seen to progressively bubble up to the top of the list
Bubble sort example:
I have printed intermediate steps to understand it better:
|
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 |
public class BubbleSortMain { /* * @author: Arpit Mandliya */ public static void main(String args[]) { int arr[]={100,20,15,30,5,75,40}; bubbleSort(arr); } public static int[] bubbleSort(int arr[]) { for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length-1-i; j++) { if(arr[j]>arr[j+1]) { int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } System.out.print("Iteration "+(i+1)+": "); printArray(arr); } return arr; } public static void printArray(int arr[]) { for (int i = 0; i <arr.length; i++) { System.out.print(arr[i]+" "); } System.out.println(); } } |
When you run above program, you will get following output:
|
1 2 3 4 5 6 7 8 9 |
Iteration 1: 20 15 30 5 75 40 100 Iteration 2: 15 20 5 30 40 75 100 Iteration 3: 15 5 20 30 40 75 100 Iteration 4: 5 15 20 30 40 75 100 Iteration 5: 5 15 20 30 40 75 100 Iteration 6: 5 15 20 30 40 75 100 Iteration 7: 5 15 20 30 40 75 100 |
You may notice that each iteration places next larger element to its correct place.
Complexity:
Best case: O(n)
Average case: O(nˆ2)
Worst case: O(nˆ2)
To understand more about complexity,please go through complexity of algorithm.
