Home / Sortings / Bubble Sort

Bubble Sort

Bubble sort also known as Sinking sort, it is a simple sort algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. First this algorithm is named as comparison sort later it is bubble sort.

Algorithm for Bubble sort:

for i = 1:n,
swapped = false
for j = n:i+1,
if a[j] < a[j-1],
swap a[j,j-1] swapped = true
→ invariant: a[1..i] in final position
break if not swapped
end

In the case of nearly sorted data, bubble sort takes O(n) time, but requires at least 2 passes through the data (whereas insertion sort requires something more like 1 pass).

Bubble sort has worst-case and average complexity both O(n2), where n is the number of items being sorted. There exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). Even other О(n2) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore, bubble sort is not a practical sorting algorithm when n is large.

Pseudo code:

procedure bubbleSort( A : list of sortable items )

n = length(A)

repeat

swapped = false

for i = 1 to n-1 inclusive do

/* if this pair is out of order */

if A[i-1] > A[i] then

/* swap them and remember something changed */

swap( A[i-1], A[i] )

swapped = true

end if

end for

until not swapped

end procedure

Time complexity of Bubble sort: O(n)
Average Performance: O(n2)
Worst case Performance: O(n2)
Best case performance: O(n)
Worst Case Space complexity: O(n) total, O(1) auxiliary.

Example for Bubble sort: Let us take the array of numbers “5 1 4 2 8”, and sort the array from lowest number to greatest number using bubble sort. In each step, elements written in bold are being compared. Three passes will be required.

First Pass

( 5 1 4 2 8 ) ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass
( 1 4 2 5 8 ) ( 1 4 2 5 8 )
( 1 4 2 5 8 ) ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )

Now, the array is already sorted, but the algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )

Program for Bubble sort:

import java.util.Scanner;

class BubbleSort {

public static void main(String []args) {

int n, c, d, swap;

Scanner in = new Scanner(System.in);

System.out.println(“Input number of integers to sort”);

n = in.nextInt();

int array[] = new int[n];

System.out.println(“Enter ” + n + ” integers”);

for (c = 0; c < n; c++)

array[c] = in.nextInt();

for (c = 0; c < ( n – 1 ); c++) {

for (d = 0; d < n – c – 1; d++) {

if (array[d] > array[d+1])

{

swap = array[d];

array[d] = array[d+1];

array[d+1] = swap;

}

}

}

System.out.println(“Sorted list of numbers”);

for (c = 0; c < n; c++){

System.out.println(array[c]);

}

}

See the output here:

Bubble Sort
Bubble sort

See the other Sorting Techniqueshere

About GSK

Hi, i am Santosh Gadagamma, a tutor in Software Engineering and an enthusiast for sharing knowledge in Computer Science and other domains. I developed this site to share knowledge to all the aspirants of technologies like, Java, C/C++, DBMS/RDBMS, Bootstrap, Big Data, Javascript, Android, Spring, Hibernate, Struts and all levels of software project design, development, deployment, and maintenance. As a programmer I believe that, "The world now needs computers to function." Hope, this site guides you as a learning tool towards greater heights. I believe that Education has no end points and i wish to learn more in the process of teaching you.

Check Also

Sorting Technique

In this blog I am going to discuss about sorting, what is sorting and how …