Every computer science student comes across the bubble sorting algorithm. It's simple and easy to translate into code. It's also referred to as the s
inking sort. Here, we'll explore Bubble Sort- How it works and how to implement it in JavaScript.
What is bubble sort?
Bubble Sort is a simple sorting technique that sorts the elements that have been placed in the wrong order by repeatedly swapping the adjacent elements.
Algorithm of bubble sort
In the algorithm below, arr is an array with n number of elements, and swap is a function that swaps the values of the array elements.
start BubbleSort(array)
if array[i] > array[i+1]
swap(array[i], array[i+1])
end if
end for
return array
end BubbleSort
Bubble sort implementation in JavaScript
Below is the code to implement bubble sort in JavaScript.
Code:
<!DOCTYPE html>
<html>
<body>
<script>
function swap(arr, xp, yp)//for swapping the values
{
var temp = arr[xp];
arr[xp] = arr[yp];
arr[yp] = temp;
}
function bubbleSort( arr, n)
{
var i, j;
for (i = 0; i < n-1; i++)
{
for (j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
swap(arr,j,j+1);
}
}
}
}
function printArray(arr, size)//prints the array
{
var i;
for (i=0; i < size; i++)
document.write(arr[i]+ " ");
document.write("\n");
}
var arr = [81, 89, 9, 11, 14, 76, 54, 22];
var n = 8;
document.write("The array before sorting:<br>");
printArray(arr, n);
bubbleSort(arr, n);
document.write("<br>The array after sorting:<br>");
printArray(arr, n);
</script>
</body>
</html>
Output:
Functioning of the bubble sort program
Here, an array arr[] has the following elements:
81,89,9,11,14,76,54,22
First iteration
Sorting start from the initial two elements. Comparing them to check which is greater
81,89,9,11,14,76,54,22
Since 81 is greater than 89 (32 > 13), there will be no changes.
Next, comparing 89 with 9,
81,89,9,11,14,76,54,22
81,9,89,11,14,76,54,22 (swap 9 with 89)
Because, 9<89
Next, comparing 9 with 11,
81,89,9,11,14,76,54,22
81,89,9,11,4,76,54,22 (no need to swap)
Because, 9<11
Next, comparing 11 with 14,
81,89,9,11,14,76,54,22
81,89,9,11,14,76,54,22 (no need to swap)
Because, 11<14
Next, comparing 14 with 76,
81,89,9,11,14,76,54,22
81,89,9,11,14,76,54,22 (no need to swap)
Because, 14<76
Next, comparing 76 with 54,
81,89,9, 11,14,76,54,22
81,9,89,11,14,54,76,22 (swap 76 with 54)
Because, 54<76
Next, comparing 76 with 22
81,9,89,11,14,54,76,22 (swap 76 with 22)
81,9,89,11,14,54,22,76
Second iteration
The same procedure gets repeated for the second operation,
Comparing 81 and 9
81,9,89,11,14,54,22,76(swap 81 with 9)
9,81,89,11,14,54,22,76
since, 9<81
Next, comparing 81 and 89
9,81,89,11,14,54,22,76 (no need to swap)
9,81,89,11,14,54,22,76
since,81<89
Next, comparing 89 and 11
9,81,89,11,14,54,22,76 (swap 89 with 11)
9,81,11,89,14,54,22,76
Since, 11<89
Next, comparing 89 and 14
9,81,11,89,14,54,22,76 (swap 89 with 14)
9,81,11,14,89,54,22,76
Since, 14<89
Next, comparing 89 and 54
9,81,11,14,89,54,22,76 (swap 89 with 54)
9,81,11,14,54,89,22,76
Since, 54<89
Next, comparing 89 and 22
9,81,11,14,54,89,22,76 (swap 89 with 22)
9,81,11,14,54,22,89,76
Since, 22<89
Next, comparing 89 and 76
9,81,11,14,54,22,89,76 (swap 76 with 89)
9,81,11,14,54,22,76,89
Since, 76<89
Third iteration
Simillarly, in the third iteration the same process gets repeated
9,81,11,14,54,22,76,89
9,81,11,14,54,22,76,89
9,81,11,14,54,22,76,89
9,11,81,14,54,22,76,89
9,11,81,14,54,22,76,89
9,11,14,81,54,22,76,89
9,11,14,81,54,22,76,89
9,11,14,54,81,22,76,89
9,11,14,54,81,22,76,89
9,11,14,54,22,81,76,89
9,11,14,54,22,81,76,89
9,11,14,54,22,76,81,89
9,11,14,54,22,76,81,89
9,11,14,54,22,76,81,89
Fourth iteration
After the fourth iteration, the elements get sorted, and the program stops.
9, 11, 14, 54, 22, 76, 81, 89
9, 11, 14, 54, 22, 76, 81, 89
9, 11, 14, 54, 22, 76, 81, 89
9, 11, 14, 54, 22, 76, 81, 89
9, 11, 14, 22, 54, 76, 81, 89
9, 11, 14, 22, 54, 76, 81, 89
9, 11, 14, 22, 54, 76, 81, 89
9, 11, 14, 22, 54, 76, 81, 89 (Resultant array elements after sorting)
Time and space complexities of Bubble Sort:
Bubble Sort’s best-case complexity is O(n) which happens when the array is already sorted.
Its average-case complexity is O(n2) which happens when the array elements are jumbled.
Its worst-case complexity is O(n2) which happens when the array elements must get sorted in reverse order.
It has a space complexity of O(n).
Conclusion:
Bubble sort is a sorting technique that sorts the elements placed in the wrong order. It is one of the simplest sorting algorithms. Because of its simplicity, Bubble Sort gets employed as an intro to sorting algorithms in elementary computer science courses.