Introduction to Bubble Sort in JavaScript
The sorting algorithm performs by repeated sorts of an array element by comparing the adjacent elements. It compares the adjacent element and swaps the element if they are in the wrong order. This algorithm repeatedly runs until all the elements in the lists are sorted. If all the elements are sorted in the list, the algorithms end automatically. Although the bubble sort algorithm is simple, it consumes more time comparing other sorting techniques. In this topic, we will learn about Bubble Sort in JavaScript.
Workflow with an Example
We have ten numbers in an array. In this case, we need to compare nine numbers to sort the largest number to the top of the array. The reason for comparing 9 numbers instead of 10 is because
n = number of elements present in the array
n – 1 = Number of times the comparison occurs
Therefore: 10 – 1 = 9.
Step 1: Compare the first two numbers, ‘2’ and ‘7’.
No swap because ‘2’ is smaller than ‘7’.
2 7 4 1 10 8 3 5 6 9
Step 2: Compare the second and third numbers’ 7′ and ‘4’.
2 4 7 1 10 8 3 5 6 9
Swap because ‘7’ is larger than ‘4’.
Step 3: Compare the third and fourth numbers’ 7′ and ‘1’.
2 4 1 7 10 8 3 5 6 9
Numbers have been swapped.
Step 4: Compare the fourth and fifth numbers’ 7′ and ’10’.
2 4 1 7 10 8 3 5 6 9
No swap because they are in order.
Step 5: Compare the fifth and sixth numbers’ 10′ and ‘8’.
2 4 1 7 8 10 3 5 6 9
They had to swap.
Step 6: Compare the sixth and seventh numbers’ 10′ and ‘3’.
2 4 1 7 8 3 10 5 6 9
They had to swap.
Step 7: Compare the seventh and eighth numbers’ 10′ and ‘5’.
2 4 1 7 8 3 5 10 6 9
They had to swap.
Step 8: Compare the eighth and ninth numbers’ 10′ and ‘6’.
2 4 1 7 8 3 5 6 10 9
They had to swap.
Step 9: Compare the ninth and tenth numbers’ 10′ and ‘9’.
2 4 1 7 8 3 5 6 9 10
They had to swap. So, as you can see from the above sort ’10’, the largest number has “bubbled” to the end of the array.
This step is repeated until the remaining 9 numbers are sorted in proper order as ‘1’ ‘2’ ‘3’ ‘4’ ‘5’ ‘6’ ‘7’ ‘8’ ‘9’ ’10’.
How does Bubble Sort work in JavaScript?
- In Bubble Sort, the algorithm will take the 1st element of the array and compare the value with the element next to it in the array.
- If the 1st element is larger than the 2nd, then the element will swap the positions.
- If it doesn’t satisfy the condition, then the algorithm will compare the 2nd element with 3rd
- This process continues until all the elements in the array is bubble sorted in the respective order.
Example:
Let’s take this below concept as an example and implement what we learned above.
This process will continue until the expected output comes, which is 12345678.
Example #1
Code:
<html>
<head>
<title> Bubble Sort </title>
</head>
<body>
<script>
var values=[];
var a=0,b=0;
document.write("<font face='arial' size='4'>BUBBLE SORT </font>");
document.write("<br><br>");
for (a=0; a<5; a++) {
values.push(Number(prompt("Enter item value at no. " + (a+1))));
}
document.write("<font face='arial' size='4'>Numbers");
document.write(" given by the user </font>");
document.write("<br><br>");
for (a=0;a<5; a++) {
document.write("<font face='arial' size='4'> " +values[a] + "");
}
for (a = 0; a < ( 5 - 1 ); a++) {
for (b = 0; b < 5 - a - 1; b++) {
if (values[b] > values[b+1])
{
swap= values[b];
values[b]= values[b+1];
values[b+1] = swap;
}
}
}
document.write("<br><br>");
document.write("<font face='arial' size='4'>Sorted List of Numbers </font>");
document.write("<br><br>");
for (a=0; a<5; a++) {
document.write("<font face='arial' size='4'> " + values[a]+"</font>");
}
</script>
</body>
Output:
Example #2
When the below program is executed, the Bubble Sort algorithm will sort the random bar chart, which will be a different size to the order as given below in the output. i.e., smallest to largest.
Code:
<html>
<head>
<title>Bubble Sort</title>
<meta charset="UTF-8">
<script src=
"https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.8.0/p5.min.js"
type="text/javascript"></script>
<style>
body {
padding: 0;
}
canvas {
vertical-align: top;
}
</style>
</head>
<body>
<script type="text/javascript">
// Set Global Variables
let values = [];
let w = 20;
// To store the state of each bar
// in order to change the color
let states = [];
function setup() {
// Create Canvas of Size Windows
// Width * Windows Height
createCanvas(800, 400);
// Insert Random values in array
values = new Array(floor(width/w));
for(let i = 0; i < values.length; i++) {
values[i] = float(random(height));
states[i] = -1;
}
// Print Unsorted Array
print("Unsorted Array:" + values);
// Call to bubble sort function
bubbleSort(values, 0, values.length);
// Print Sorted Array
print("Sorted Array:" + values);
}
// Definition of bubble sort
async function bubbleSort(arr, start, end) {
if(start >= end) {
return;
}
for(var i = 0; i < end-1; i++) {
for(var j = 0; j < end-i-1; j++) {
if(arr[j] >= arr[j+1]) {
states[j] = 1;
// Call to swap function
await swap(arr, j, j+1);
states[j+1] = 0;
}
states[j] = 2;
}
}
return arr;
}
// Definition of draw function
function draw() {
background(51);
for(let i = 0; i < values.length; i++) {
stroke(0);
fill(255);
if(states[i] == 0) {
fill(255, 0, 0);
}
else if (states[i] == 1) {
// Element currently sorting
fill("#58FA82");
}
else {
fill(255);
}
rect(i*w, height - values[i], w, values[i]);
}
}
// Definition of swap function
async function swap(arr, a, b) {
await sleep(20);
let t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
// Definition of sleep function
function sleep(ms) {
return new Promise(resolve => setTimeout(resolve, ms));
}
</script>
</body>
</html>
Output:
Conclusion
Bubble Sort is the most inefficient algorithm. We should compare all the elements with each element in the array in the sorting algorithm. Hence, you will not use Bubble Sort to sort the elements in everyday code. Even though the Bubble Sort technique is the most inefficient algorithm, the programmer uses it more frequently due to its simplicity.
Recommended Articles
This is a guide to Bubble Sort in JavaScript. Here we discuss the basic concept, how Bubble Sort works in JavaScript, and examples. You may also look at the following article to learn more –