Bubble sort is an algorithm for sorting elements by repeatedly comparing adjacent pairs and swapping them if they are in the wrong order until the entire list is sorted.
We will sort based on ascending order.
How Bubble Sort Works:
Traverse from the left and compare adjacent elements and the higher one is placed on the right side.
The largest element is moved to the rightmost end at first.
Then continue to find the second largest and place it until the data is sorted.
Algorithm:
for i <- 1 to indexOfLastUnsortedElement-1
if leftElement > rightElement
swap leftElement and rightElement
end bubbleSort
JavaScript Implementation:
bubbleSort(arr); // bubbleSort() function call.
function bubbleSort(arr){
let n = arr.length; // ‘n’ is array size.
for (let j=0; j<n–1; ++j){
for (let i=0; i<n–j–1; ++i){
if (arr[i] > arr[i+1]){
let temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
console.log(arr); // Print the Sorted Arry.
}
Output:
How we can optimize the bubble sort algorithm?
All the comparisons are made in the above algorithm even if the array is already sorted. This increases the execution time.
We can optimize by checking if the elements are sorted or not. The value of swapped is set to 1 (true) if there occurs a swapping of elements. Otherwise, it is set to 0 (false).
This will reduce the execution time to optimize the bubble sort.
Optimized Bubble Sort Algorithm
swapped <- false
for i <- 1 to indexOfLastUnsortedElement-1
if leftElement > rightElement
swap leftElement and rightElement
swapped <- true
end bubbleSort
bubbleSort(arr); // bubbleSort() function call.
function bubbleSort(arr){
let swapped = 0; // check if swapping occurs
let n = arr.length; // ‘n’ is array size.
for (let j=0; j<n–1; ++j){
for (let i=0; i<n–j–1; ++i){
if (arr[i] > arr[i+1]){
let temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = 1;
}
}
// no swapping means the array is already sorted. so no need for further comparison.
if (swapped == 0) {
break;
}
}
console.log(arr); // Print the Sorted Arry.
}
Output:
Time Complexity: O(N^2)
Thanks for Reading 🩵⭐
Reference:
https://www.programiz.com/dsa/bubble-sort
https://www.geeksforgeeks.org/bubble-sort/
https://www.geeksforgeeks.org/time-and-space-complexity-analysis-of-bubble-sort/
