Algorithms - Sorting (Bubble Sort)

bubbleSort.js

/*
    Bubble sort 
    - Time complexity O(n^2)
    - Best use case if array is almost sorted
*/

function bubbleSort(arr) {
    // Swap flag for inner iteration
    let swap = false;
    // Iterate from end of array to beginning of the array to determine the end point of the inner iteration
    // Inner iteration can exclude the last element because it has already been sorted!
    for(let i = arr.length; i > 0; i--) {
        // Inner iteration to check if current val is greater than next val
        // Ends at i - 1 because after the swaping, the last element is already sorted
        for (let j = 0; j < i - 1; j++) {
            // Swap if current val is greater than next val
            if(arr[j] > arr[j+1]) [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            swap = true;
        }
        // If no swaps happened in inner iteration break out of loop - for optimization
        if (!swap) break;
    }
    return arr;
}

bubbleSort([3, 23, 67, 2, 5, 76, 54, 90, 102, 4, 7, 32, 13]); //[2, 3, 4, 5, 7, 13, 23, 32, 54, 67, 76, 90, 102]