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