Bubble sort in java

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.

Table of Contents

Bubble sort algorithm
Bubble sort Implementation
Time Complexity:

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 Implementation

I have printed intermediate steps to understand it better:

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 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.

Time 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.

Author

Algorithm Interview Sorting

04 November

Topological Sort in java

Table of ContentsTopological Sort exampleTopological Sort AlgorithmWhy it works?Java program to implement topological sortingTime Complexity In this post, we will see about Topological Sorting in the graph. Topological Sorting is ordering of vertices or nodes such if there is an edge between (u,v) then u should come before v in topological sorting. Topological sort is […]

Array Sorting

23 August

Sort array in java

Table of ContentsJava Sort ArraySort Array of numbersSort Array of StringsSort array of custom objects In this post, we will see how to sort an array in java. There are various ways to sort array in java. You can implement different sorting algorithms to sort an array. You can use Arrays.sort method to sort array […]

Algorithm Interview Sorting

12 October

Selection sort in java

Table of ContentsSelection sort algorithmSelection sort algorithmTime complexity If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview programs. Selection sort is an in place comparison sorting algorithm. It is very simple to implement but it does not go well with large number of inputs. Selection sort […]

Algorithm Interview Sorting

12 October

Shell sort in java

Shell sort is in place comparison based sorting algorithm. It is generalization of insertion sort. It was invented by Donald shell. It allows to sort elements which are far apart. In case of insertion sort, comparison happens between only adjacent elements but in shell sort, it avoid comparing adjacent elements until last steps. Last step of shell […]

Algorithm Interview Sorting

12 October

Quick Sort in java

Table of ContentsQuick sort AlgorithmQuick Sort implementationTime complexity If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions. Quick sort or partition-exchange sort, is a sorting algorithm, which is using divide and conquer algorithm. In quick sort, we first choose a pivot and divide into two sublists,one […]

Algorithm Interview Sorting

12 October

Counting Sort in java

Table of ContentsSteps for Counting Sort:Java program for counting sort: Counting sort is special sorting technique used to sort elements between specific range. Lets say elements belong to range 1 to K , then Counting sort can be used to sort elements in O(N) times. Basic idea of counting sort to find number of elements […]

Bubble sort in java