Sorting Algorithm
In this tutorial, we will learn about Bubble Sort which is one of the easiest sorting algorithms.
We use Bubble Sort algorithm to sort the elements in either ascending or descending order.
We compare two adjacent elements and swap them only if they are not in the correct position.
(n – 1) pass to sort an array arr having n elements.arr[i] and arr[i + 1] are compared and if they are not in order then they are swapped.(n – k) comparisons, where n is the number of elements and k is the pass number.So, if an unsorted array has n elements then we will need total (n - 1) pass to sort the elements in either ascending or descending order.
And in any given pass k, we will make (n - k) comparison.
/**
* a[0:n-1] is an array of n elements.
* temp is a variable to facilitate exchange.
*/
BubbleSort(a, n)
Begin
for k = 1 to n-1 increment by 1 do // where, k is for the pass
for j = 0 to n – k – 1 increment by 1 do // this is for comparison
if a[j] > a[j+1] then
Set temp = a[j];
Set a[j] = a[j+1];
Set a[j+1] = temp;
endif
endfor
endfor
End
Let's say we have the following unsorted numbers 5, 4, 3, 1, 2 and we want to sort them in ascending order.
So, there are total 5 elements. Hence we will need (5 - 1) i.e. 4 pass.
In Pass #1 we will perform (n - k) i.e. (5 - 1) i.e. 4 comparisons.
Start: 5, 4, 3, 1, 2
Compare 5 and 4: swap as they are not in order
[5, 4], 3, 1, 2 ---> 4, 5, 3, 1, 2
Compare 5 and 3: swap as they are not in order
4, [5, 3], 1, 2 ---> 4, 3, 5, 1, 2
Compare 5 and 1: swap as they are not in order
4, 3, [5, 1], 2 ---> 4, 3, 1, 5, 2
Compare 5 and 2: swap as they are not in order
4, 3, 1, [5, 2] ---> 4, 3, 1, 2, 5
End: 4, 3, 1, 2, 5
In Pass #2 we will perform (5 - 2) i.e. 3 comparisons.
Start: 4, 3, 1, 2, 5
Compare 4 and 3: swap as they are not in order
[4, 3], 1, 2, 5 ---> 3, 4, 1, 2, 5
Compare 4 and 1: swap as they are not in order
3, [4, 1], 2, 5 ---> 3, 1, 4, 2, 5
Compare 4 and 2: swap as they are not in order
3, 1, [4, 2], 5 ---> 3, 1, 2, 4, 5
End: 3, 1, 2, 4, 5
In Pass #3 we will perform (5 - 3) i.e. 2 comparisons.
Start: 3, 1, 2, 4, 5
Compare 3 and 1: swap as they are not in order
[3, 1], 2, 4, 5 ---> 1, 3, 2, 4, 5
Compare 3 and 2: swap as they are not in order
1, [3, 2], 4, 5 ---> 1, 2, 3, 4, 5
End: 1, 2, 3, 4, 5
In Pass #4 we will perform (5 - 4) i.e. 1 comparison.
Start: 1, 2, 3, 4, 5
Compare 1 and 2: they are in order so, no swapping required
1, 2, 3, 4, 5 ---> 1, 2, 3, 4, 5
End: 1, 2, 3, 4, 5
And we have the elements sorted in ascending order using Bubble Sort algorithm.
In the following section we have Bubble Sort in Java, C, PHP, Python and JavaScript.
#include <stdio.h>
//function declaration
void bubbleSort(int *a, int n);
int main(){
//variable declaration
int arr[5], i;
//input
for(i = 0; i < 5; i++)
scanf("%d", &arr[i]);
//sort
bubbleSort(arr,5); //sending arr address and no. of elements
//output
for(i = 0; i < 5; i++)
printf("%d\n", arr[i]);
return 0;
}
//function definition
void bubbleSort(int *a, int n){
int k, j, temp;
for(k = 1; k <= n-1; k++){
for(j = 0; j <= n-k-1; j++){
if(a[j] > a[j+1]){
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
public class BubbleSort {
public static void main(String args[]) {
// unsorted array
int arr[] = {5, 4, 3, 1, 2};
// total elements in the array
int len = arr.length;
int k, j, temp;
// sorting
for(k = 1; k <= len - 1; k++) {
for(j = 0; j <= len - k - 1; j++) {
if(arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
// result
for(k = 0; k < len; k++) {
System.out.print(arr[k] + " ");
}
}
}
<?php
// unsorted array
$arr = [5, 4, 3, 1, 2];
// number of elements in the array
$len = count($arr);
// sorting
for($k = 1; $k <= $len - 1; $k++) {
for($j = 0; $j <= $len - $k - 1; $j++) {
if($arr[$j] > $arr[$j + 1]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
}
}
}
// print sorted elements
foreach($arr as $k) {
print($k . " ");
}
// unsorted array
arr = [5, 4, 3, 1, 2]
// number of elements in the array
length = len(arr)
// sorting
for k in range(1, length):
for j in range(0, length - k):
if arr[j] > arr[j + 1]:
temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
// print sorted elements
for item in arr:
print(item)
// unsorted array
var arr = [5, 4, 3, 1, 2];
// number of elements in the array
var len = arr.length;
// sorting
for(var k = 1; k <= len - 1; k++) {
for(var j = 0; j <= len - k - 1; j++) {
if(arr[j] > arr[j + 1]) {
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
// print sorted elements
for(var i = 0; i < len; i++) {
console.log(arr[i]);
}
Worst-case and average time complexity of Bubble sort is O(n2), where n is the number of items being sorted.
When n is very large then Bubble sort is not a suitable choice to sort the elements.
Check out Quick Sort.
ADVERTISEMENT