If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
Table of Contents
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)
Reason for being called Sinking sort
sink
to the bottom of the list
Reason for being called Bubble sort
bubble
up to the top of the listBubble sort Implementation
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:
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.
Time Complexity:
O(n)
O(n^2)
O(n^2)