JavaScriptAlgorithms/Sorts/BubbleSort.js at master · manojsdeveloper/JavaScriptAlgorithms · GitHub

History

60 lines (54 loc) · 1.52 KB

Raw

/* 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

}

JavaScriptAlgorithms/Sorts/BubbleSort.js at master · manojsdeveloper/JavaScriptAlgorithms · GitHub

Expand file tree

Breadcrumbs

BubbleSort.js

Latest commit

History

Breadcrumbs

BubbleSort.js

File metadata and controls