//bubble, selection, quick, merge sort

const input = [5, 3, 4, 2, 7];

//bubble sort: iterate list, compare adjacent items,
//swap them if they are out of order, repeat until no swaps in one iteration
// O(n^2) worst case time, because each element compared with each other element
// actually it is like: (n-1) comp + (n-2) comp + ... + (1) comp
// sum of i=1 to i=n of (n - i)
//simplifies to O(n^2) big O

const bubbleSort = arr => {
    //compare current index to next index
    // swap if next is smaller than current
    let i = 0;
    let sorted = false;
    while (!sorted) {
        sorted = true;
        for (i=0; i < arr.length-1; i++) {
            if (arr[i] > arr[i+1]) {
                [arr[i], arr[i+1]] = [arr[i+1], arr[i]];
                sorted = false;
            }
        }
        i = 0;
    }

    return arr;
}

console.log(bubbleSort(input));

//selection sort: find smallest element in unsorted array, place at front of new array
// repeat on remaining elements of unsorted array
// O(n) run time bc just iterating through n elements in the array

const input2 = [5, 3, 4, 2, 7];

const selectionSort = arr => {

    const sorted = [];
    const len = arr.length; //cant use arr.length actively in for-loop as arr is mutated

    for (let i = 0; i < len; i++) {
        const min = Math.min(...arr);
        sorted.push(min);
        arr.splice(arr.indexOf(min), 1);
    }
    return(sorted);
}

console.log(selectionSort(input2));

// quicksort:

let input3 = [7, 4, 2, 3, 6, 5, 11, 16, 9];
const left = [];
const right = [];

//1 choose any element in array [p..r]
// call this element 'pivot'
// rearrange [p..r] with smaller on left and greater on right
// actually always call rightmost element pivot
// recursively sort subarray
// now it is sorted

const quickSort = (arr, left, right) => {
    //choose pivot
    //put smaller on left of pivot
    //put smaller on right of pivot
    //sort array(s) on left of pivot
    //sort array(s) on right of pivot
    const pivot = arr[arr.length-1];
    console.log(pivot);

    arr.forEach(element => {
        console.log(arr);
        console.log(element);
        if (element < pivot) {
            console.log(element);
            left.push(element);
        } else if (element > pivot) {
            console.log(element);
            right.push(element);
        }
    })

    if (left.length > 1) {
        left = quickSort(left, [], []);
    }
    if (right.length > 1) {
        right = quickSort(right, [], []);
    }
    arr = [...left, pivot, ...right];

    console.log(arr);

    return arr;
}

console.log(quickSort(input3, left, right));

//mergesort - also divide and conquer
// 1 - divide problems to smaller instances of same problem (subproblems)
// 2- solve subproblems recursively. when possible, solve base case.
// 3- combine solutions for subproblem into solution for original problem

// divide array into two arrays about the middle
// repeat until arrays are size 0 or 1
// 'merge' two arrays ie [2, 4] [7, 8] --> [2, 4, 7, 8]

let input4 = [5, 3, 4, 2, 7, 9, 2, 1];

const merge = (arr1, arr2) => {
    const arr3 = [];
    const newLen = arr1.length + arr2.length

    while(arr3.length < newLen) {
        if (arr1.length > 0 && arr2.length > 0) {
            console.log(arr3);
            console.log(arr1.length);
            console.log(arr2.length);
            arr3.push((arr1[0] < arr2[0]) ? arr1.shift() : arr2.shift());
        }
        else if (arr1.length > 0) arr3.push(arr1.shift());
        else if (arr2.length > 0) arr3.push(arr2.shift());
    }
    console.log(arr3);
    return arr3;
}

const mergeSort = (arr) => {
    console.log(arr);
    const mid = Math.floor(arr.length / 2);
    let left = arr.slice(0, mid); //slice --> starting at, ending at (NOT inclusive)
    let right = arr.slice(mid, arr.length);
    console.log(left);
    console.log(right);
    if (left.length > 1) {
        left = mergeSort(left);
    }
    if (right.length > 1) {
        right = mergeSort(right);
    }
    console.log(left);
    console.log(right);
    arr = merge(left, right);
    console.log(arr);
    return arr;
}

// let b = [3, 9];
// let c = [2, 11];
// merge(b, c);
input4 = mergeSort(input4);
//merge([3,5],[2,4]);
console.log(input4);