Introduction
Bubble sort is well known algorithm to sort. However, are you sure that the bubble sort you know is most efficient? This article is going to talk about how to use bubble sort efficiently. Before getting started, let's remind what is bubble sort.
Bubble Sort
Bubble sort is named because it looks like bubble up. Bubble sort is a simple sorting algorithm
- traverse from left and compare adjacent elements and the higher one is placed at right side.
- In this way, the largest element is moved to the rightmost end at first.
- This process is then continued to find the second largest and place it and so on until the data is sorted.
Code
It is easy to implement bubble sort. Just use two loops and if element is bigger than next element, swap the elements.
js
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
isSwapped = true
// Swap
let temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
}
const arr = [2, 9, 6, 5, 8];
bubbleSort(arr);
Optimized Bubble Sort
There is a way to optimize bubble sort with above codes. If array is completely sorted during sorting, there is no need to proceed further. Therefore, just break (stop) looping if it's sorted.
js
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
let isSwapped = false
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
isSwapped = true
// Swap
let temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
// Swap이 일어나지 않음
if(!isSwapped) break
}
}
const arr = [2, 9, 6, 5, 8];
bubbleSort(arr);
If there is no swapped process, just get out of loop with break Syntax.