BubbleSort.js

/* Bubble Sort is an algorithm to sort an array. It
 * compares adjacent element and swaps their position
 * The big O on bubble sort in worst and best case is O(N^2).
 * Not efficient.
 * Somehow if the array is sorted or nearly sorted then we can optimize bubble sort by adding a flag.
 *
 * 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.
 *
 * Wikipedia: https://en.wikipedia.org/wiki/Bubble_sort
 * Animated Visual: https://www.toptal.com/developers/sorting-algorithms/bubble-sort
 */

/**
 * Using 2 for loops.
 */
export function bubbleSort(items) {
 const length = items.length
 let noSwaps

 for (let i = length; i > 0; i--) {
 // flag for optimization
 noSwaps = true
 // Number of passes
 for (let j = 0; j < i - 1; j++) {
 // Compare the adjacent positions
 if (items[j] > items[j + 1]) {
 // Swap the numbers
 ;[items[j], items[j + 1]] = [items[j + 1], items[j]]
 noSwaps = false
 }
 }
 if (noSwaps) {
 break
 }
 }

 return items
}

/**
 * Using a while loop and a for loop.
 */
export 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
}