bubble sort, values go up like a bubble

Bubble Sort Pseudocode

• Start looping from with a variable called i the end of the array towards the beginning

• Start an inner loop with a variable called j from the beginning until i - 1

• If arr[j] is greater than arr[j+1], swap those two values

• Return sorted array

function bubbleSort(arr) {
    const swap = (arr, idx1, idx2) => {
        [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]
    };

    for(let i = arr.length; i>0; i--) {
        for(let j = 0; j < i - 1; j++) {
            if(arr[j] > arr[j+1]) {
                swap(arr, j, j+1);
            }
        }
    }
    return arr;
}

Bubble sort Big O notation

O(n^2) usally, but if is already almost sorted then its much faster.

---

Selection Sort Pseudocode

• Store the first element as the smallest value you've seen so far

• Compare this item to the next item in the array until you find a smaller number

• If a smaller number is found, designate that smaller number to be the new "minimum" and continue until the end of the array.

• If the "minimum" is not the value you initially began with, swap the two values.

• Repeat this with the next element until the array is sorted.

function selectionSort(arr) {
    for( let i = 0; i < arr.length ; i++) {
        let lowest = i;
        for ( let j = i + 1; j < arr.length; j++) {
            if(arr[j] < arr[lowest]) {
                lowest = j;
            }
        }
        let temp = arr[i];
        arr[i] = arr[lowest];
        arr[lowest] = temp;
    }
    return arr;
}
selectionSort([1,3,2,5,9,7]) // [1,2,3,4,7,9]

O(n^2) time complexity

we have to compare every single element...

---

Insertion Sort Pseudocode

• Start by picking up the second element in the array

• Now compare the second element with the one before it and swap if necessary

• Continue to the next element and if is in the incorrect order, iterate through the sorted portion to place the element in the correct place.

• Repeat until the array is sorted

function insertionSort(arr) {
    for(let i = 1; i < arr.length; i++) {
        let currentVal = arr[i];
        for(let j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
            arr[j+1] = arr[j];
        }
        arr[j+1] = currentVal;
    }
}

insertionSort([3,1,5,90,4]) // [1,3,4,5,90]