IT2EDU Empowering Education Through Technology
Related Articles
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:
See the other Sorting Techniqueshere
