bubblesort Algorithm
Bubble Sort is a simple and widely recognized sorting algorithm that operates by repeatedly stepping through the list of items to be sorted, comparing each pair of adjacent elements, and swapping them if they are in the wrong order. This process continues until the entire list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list while larger elements "sink" to the bottom. Due to its simplicity, Bubble Sort is often used as an introductory sorting algorithm for teaching purposes.
However, Bubble Sort is not the most efficient sorting algorithm. In the worst-case scenario, it has a time complexity of O(n^2), meaning that the number of operations it requires increases quadratically with the number of elements to be sorted. This makes Bubble Sort inefficient for large datasets, and it is generally outperformed by other sorting algorithms such as Quick Sort, Merge Sort, and Heap Sort. Despite its inefficiency, Bubble Sort can still be a suitable choice for small datasets or as part of a hybrid sorting approach, wherein Bubble Sort is used to sort small subarrays within a larger sorting algorithm.
/* Bubble Sort is a algorithm to sort an array. It
* compares adjacent element and swaps thier position
* The big O on bubble sort in worst and best case is O(N^2).
* Not efficient.
*/
function bubbleSort (items) {
const length = items.length
for (let i = (length - 1); i > 0; i--) {
// Number of passes
for (let j = (length - i); j > 0; j--) {
// Compare the adjacent positions
if (items[j] < items[j - 1]) {
// Swap the numbers
[items[j], items[j - 1]] = [items[j - 1], items[j]]
}
}
}
}
// Implementation of bubbleSort
var ar = [5, 6, 7, 8, 1, 2, 12, 14]
// Array before Sort
console.log('-----before sorting-----')
console.log(ar)
bubbleSort(ar)
// Array after sort
console.log('-----after sorting-----')
console.log(ar)
/* alternative implementation of bubble sort algorithm.
Using a while loop instead. For educational purposses only
*/
/*
*In bubble sort, we keep iterating while something was swapped in
*the previous inner-loop iteration. By swapped I mean, in the
*inner loop iteration, we check each number if the number proceeding
*it is greater than itself, if so we swap them.
*/
function alternativeBubbleSort (arr) {
let swapped = true
while (swapped) {
swapped = false
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]
swapped = true
}
}
}
return arr
}
// test
console.log('-----before sorting-----')
var array = [10, 5, 3, 8, 2, 6, 4, 7, 9, 1]
console.log(array)
console.log('-----after sorting-----')
console.log(alternativeBubbleSort(array))
