// -------------------------------------------------------------------------------------------------------------------- //
Guess What Algo

// --------------------------------------------------------------------------------------------------------------------

<===================~~==-----==()==-----==~~==========================>

// HINTS:

// divide and conquer // need a helper function that solves merging elements of two sorted arrays into a single sorted array

function guessWhatAlgo(array) {
    if (array.length <= 1) {
        return array;
    }

    let midIdx = Math.floor(array.length / 2);

    let leftHalf = array.slice(0, midIdx);
    let rightHalf = array.slice(midIdx);

    let sortedLeft = guessWhatAlgo(leftHalf);
    let sortedRight = guessWhatAlgo(rightHalf);

    return helperguessWhatAlgo(sortedLeft, sortedRight);
}

// ANSWER: Merge sort

// if there is only one element in the list, it is already sorted.return that array. // otherwise, divide the list recursively into two halves until it can no more be divided. // merge the smaller lists into new list in sorted order.

// TIME COMPLEXITY: O(nlogn)

// SPACE COMPLEXITY:O(n)

<===================~~==-----==()==-----==~~==========================>

// HINT:

// works by performing multiple passes to move elements closer to their final positions

function guessWhatAlgo(array) {
    let swapped = true;
    while (swapped) {
        // O(n)
        swapped = false;

        for (let i = 0; i < array.length; i++) {
            //O(n)

            if (array[i] > array[i + 1]) {
                swap(array, i, i + 1);

                swapped = true;
            }
        }
    }

    return array;
}

// ANSWER: Bubble sort

// TIME COMPLEXITY: O(n * n === n^2)

// SPACE COMPLEXITY: O(1)

<===================~~==-----==()==-----==~~==========================>

// HINT:

function guessWhatAlgo(array) {
    if (array.length <= 1) {
        return array;
    }

    let pivot = array.shift();
    let left = array.filter((el) => el < pivot);
    let right = array.filter((el) => el >= pivot);

    let leftSorted = guessWhatAlgo(left);
    let rightSorted = guessWhatAlgo(right);

    return [...leftSorted, pivot, ...rightSorted];
}

// ANSWER: Quick sort

// TIME COMPLEXITY: worst case: O(n^2) best case: O(nlogn)

// SPACE COMPLEXITY:O(n)

<===================~~==-----==()==-----==~~==========================>

function guessWhatAlgo(arr) {
    for (let i = 1; i < arr.length; i++) {
        let currElement = arr[i];
        for (var j = i - 1; j >= 0 && currElement < arr[j]; j--) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = currElement;
    }
    return arr;
}

// ANSWER: Insertion sort

// TIME COMPLEXITY: O(n^2)

// SPACE COMPLEXITY:O(1)

<===================~~==-----==()==-----==~~==========================>

function guessWhatAlgo(array, target) {
    if (array.length === 0) {
        return false;
    }

    let midIdx = Math.floor(array.length / 2);

    if (target < array[midIdx]) {
        let leftHalf = array.slice(0, midIdx);

        return guessWhatAlgo(leftHalf, target);
    } else if (target > array[midIdx]) {
        let rightHalf = array.slice(midIdx + 1);

        return guessWhatAlgo(rightHalf, target);
    } else {
        return true;
    }
}

// ANSWER: Binary Search

// TIME COMPLEXITY: O(logn)

// SPACE COMPLEXITY:O(n) ]

<===================~~==-----==()==-----==~~==========================>

function guessWhatAlgo(arr) {
    for (let i = 0; i < arr.length; i++) {
        let minIndex = i;

        for (let j = i + 1; j < arr.length; j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
        }

        swap(arr, i, minIndex);
    }
    return arr;
}

// ANSWER: Selection sort

// TIME COMPLEXITY: O(n^2)

// SPACE COMPLEXITY:O(1)

![selection](

![selection](

// Use this pseudocode to implement the bubble sort function bubbleSort(array) { // n := length(array) // repeat // swapped = false // for i := 1 to n - 1 inclusive do // // /* if this pair is out of order / // if A[i - 1] > A[i] then // // / swap them and remember something changed */ // swap(A[i - 1], A[i]) // swapped := true // // end if // end for // until not swapped }

function swap(array, idx1, idx2) {
    let temp = array[idx1]; // save a copy of the first value
    array[idx1] = array[idx2]; // overwrite the first value with the second value
    array[idx2] = temp; // overwrite the second value with the first value
}

function bubbleSort(array) {
    // this variable will be used to track whether or not we
    // made a swap on the previous pass. If we did not make
    // any swap on the previous pass, then the array must
    // already be sorted
    let swapped = true;

    // this while will keep doing passes if a swap was made
    // on the previous pass

    while (swapped) {
        swapped = false; // reset swap to false

        // this for will perform a single pass
        for (let i = 0; i < array.length; i++) {
            // if the two value are not ordered...
            if (array[i] > array[i + 1]) {
                // swap the two values
                swap(array, i, i + 1);

                // since you made a swap, remember that you did so
                // b/c we should perform another pass after this one
                swapped = true;
            }
        }
    }

    return array;
}

// Try to implement swap on your own, this time.
function swap(arr, index1, index2) {}

function selectionSort(list) {
    // list  : array of items
    // n     : size of list
    //
    // for i = 1 to n - 1
    // /* set current element as minimum*/
    //    min = i
    //
    //    /* check the element to be minimum */
    //
    //    for j = i+1 to n
    //       if list[j] < list[min] then
    //          min = j;
    //       end if
    //    end for
    //
    //    /* swap the minimum element with the current element
    //       using the above swap function*/
    //    if indexMin != i  then
    //       swap list[min] and list[i]
    //    end if
    // end for
}


function selectionSort(arr) {
    // the `i` loop will track the index that points to the first element of the unsorted region:
    //    this means that the sorted region is everything left of index i
    //    and the unsorted region is everything to the right of index i
    for (let i = 0; i < arr.length; i++) {
        let minIndex = i;

        // the `j` loop will iterate through the unsorted region and find the index of the smallest element
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
        }

        // after we find the minIndex in the unsorted region,
        // swap that minIndex with the first index of the unsorted region
        swap(arr, i, minIndex);
    }
    return arr;
}

function insertionSort(list) {
    // for i from 1 to length(list) inclusive do:
    //   /* select value to be inserted */
    //   valueToInsert = list[i]
    //   holePosition = i
    //   /* locate hole position for the element to be inserted */
    //   while holePosition > 0 and list[holePosition-1] > valueToInsert do:
    //     list[holePosition] = list[holePosition-1]
    //     holePosition = holePosition -1
    //   end while
    //   /* insert the number at hole position */
    //   list[holePosition] = valueToInsert
    // end for
}

// All 3 implementations work the same, just a reworking of syntax

// Insertion sort keeps a sorted left region working from left to right examining 
// each item and comparing it to items on its left. It then inserts the item in 
// the correct oposition in the array.
function insertionSortV2(arr) {
    for (let i = 1; i < arr.length; i++) {
        let j = i;
        while (j > 0 && arr[j - 1] > arr[j]) {
            swap(arr, j - 1, j);
            j--;
        }
    }
    return arr;
}

function swap(arr, index1, index2) {
    let temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

// The version below swaps out the for loop for a while loop to avoid using var
function insertionSortV2(arr) {
    // the `i` loop will iterate through every element of the array
    // we begin at i = 1, because we can consider the first element of the array as a
    // trivially sorted region of only one element
    // insertion sort allows us to insert new elements anywhere within the sorted region
    for (let i = 1; i < arr.length; i++) {
        // grab the first element of the unsorted region
        let currElement = arr[i];

        // the `j` loop will iterate left through the sorted region,
        // looking for a legal spot to insert currElement
        let j = i - 1;
        // keep moving left while currElement is less than the j-th element
        while (j >= 0 && currElement < arr[j]) {
            arr[j + 1] = arr[j];
            // the line above will move the j-th element to the right,
            // leaving a gap to potentially insert currElement
            // we have to remember to decrement in our while loop!
            j--;
        }
        // insert currElement into that gap
        arr[j + 1] = currElement;
    }
    return arr;
}


// This solution utilizes var in the inner for loop to be able to use the variable
// after the loop exits. I generally try to avoid var because of the complications
// it can present.
function insertionSortV3(arr) {
    // the `i` loop will iterate through every element of the array
    // we begin at i = 1, because we can consider the first element of the array as a
    // trivially sorted region of only one element
    // insertion sort allows us to insert new elements anywhere within the sorted region
    for (let i = 1; i < arr.length; i++) {
        // grab the first element of the unsorted region
        let currElement = arr[i];

        // the `j` loop will iterate left through the sorted region,
        // looking for a legal spot to insert currElement
        for (var j = i - 1; j >= 0 && currElement < arr[j]; j--) {
            // keep moving left while currElement is less than the j-th element

            arr[j + 1] = arr[j];
            // the line above will move the j-th element to the right,
            // leaving a gap to potentially insert currElement
        }
        // insert currElement into that gap
        arr[j + 1] = currElement;
    }
    return arr;
}

function merge(array1, array2) {
    // var result as array
    // while ( a and b have elements )
    //   if ( a[0] > b[0] )
    //     add b[0] to the end of result
    //     remove b[0] from b
    //   else
    //     add a[0] to the end of result
    //     remove a[0] from a
    //   end if
    // end while
    // while ( a has elements )
    //   add a[0] to the end of result
    //   remove a[0] from a
    // end while
    // while ( b has elements )
    //   add b[0] to the end of result
    //   remove b[0] from b
    // end while
    // return result
}

function mergeSort(array) {
    // if ( n == 1 ) return a
    // /* Split the array into two */
    // var l1 as array = a[0] ... a[n/2]
    // var l2 as array = a[n/2+1] ... a[n]
    // l1 = mergesort( l1 )
    // l2 = mergesort( l2 )
    // return merge( l1, l2 )
}


function merge(array1, array2) {
    let merged = [];

    while (array1.length || array2.length) {
        let ele1 = array1.length ? array1[0] : Infinity;
        let ele2 = array2.length ? array2[0] : Infinity;

        let next;
        if (ele1 < ele2) {
            next = array1.shift();
        } else {
            next = array2.shift();
        }

        merged.push(next);
    }

    return merged;
}



function mergeSort(array) {
    if (array.length <= 1) {
        return array;
    }

    let midIdx = Math.floor(array.length / 2);
    let leftHalf = array.slice(0, midIdx);
    let rightHalf = array.slice(midIdx);

    let sortedLeft = mergeSort(leftHalf);
    let sortedRight = mergeSort(rightHalf);

    return merge(sortedLeft, sortedRight);
}

function quickSort(array) {
    // if the length of the array is 0 or 1, return the array
    // set the pivot to the first element of the array
    // remove the first element of the array
    // put all values less than the pivot value into an array called left
    // put all values greater than the pivot value into an array called right
    // call quick sort on left and assign the return value to leftSorted
    // call quick sort on right and assign the return value to rightSorted
    // return the concatenation of leftSorted, the pivot value, and rightSorted
}


function quickSort(array) {
    if (array.length <= 1) {
        return array;
    }

    let pivot = array.shift();
    let left = array.filter((el) => el < pivot);
    let right = array.filter((el) => el >= pivot);

    let leftSorted = quickSort(left);
    let rightSorted = quickSort(right);

    return [ ...leftSorted, pivot, ...rightSorted ];
}