Sort

function bubbleSort(arr) {
    for(let i=0, len=arr.length;i < len-1;i++) {
        for(let j=0;j < len-i-1;j++) {
            if(arr[j] > arr[j+1]) {
                arr[j] += arr[j+1];
                arr[j+1] = arr[j] - arr[j+1];
                arr[j] = arr[j] - arr[j+1];
            }
        }
    }
    return arr;
}
console.log("bubbleSort", bubbleSort([5,2,3,9,1,2,7,3]));

function selectionSort(arr) {
    for(let i=0, len=arr.length;i < len-1;i++) {
        let minVal = arr[i], minIndex = i;
        for(let j=i+1;j < len;j++) {
            if(arr[j] < minVal) {
                minVal = arr[j];
                minIndex = j;
            }
        }
        arr[minIndex] = arr[i];
        arr[i] = minVal;
    }
    return arr;
}
console.log("selectionSort", selectionSort([5,2,3,9,1,2,7,3]));

function insertionSort(arr) {
    for(let i=1, len=arr.length;i < len;i++) {
        for(let j=i;j > 0;j--) {
            if(arr[j] < arr[j-1]) {
                arr[j] += arr[j-1];
                arr[j-1] = arr[j] - arr[j-1];
                arr[j] = arr[j] - arr[j-1];
            }else {
                break;
            }
        }
    }
    
    return arr;
}
console.log("insertionSort", insertionSort([5,2,3,9,1,2,7,3]));

function mergeSort(arr) {
    const len = arr.length;
    if(len <= 1) {
        return arr;
    }
    const mid = Math.floor(len/2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    arr = [];
    let leftIndex = 0, rightIndex = 0;
    while(left[leftIndex] !== undefined || right[rightIndex] !== undefined) {
        if(right[rightIndex] === undefined || (left[leftIndex] !== undefined && left[leftIndex] <= right[rightIndex])) {
            arr.push(left[leftIndex]);
            leftIndex++;
        }else {
            arr.push(right[rightIndex]);
            rightIndex++;
        }
    }
    return arr;
}
console.log("mergeSort", mergeSort([5,2,3,9,1,2,7,3]));

function quickSort(arr) {
    const len = arr.length;
    if(len <= 1) {
        return arr;
    }
    let pivot = len - 1, i = 0;
    while(pivot > i) {
        if(arr[i] > arr[pivot]) {
            if(i === pivot-1) {
                arr[pivot] = arr[i]+arr[pivot];
                arr[i] = arr[pivot] - arr[i];
                arr[pivot] = arr[pivot] - arr[i];
            }else {
                const temp = arr[pivot-1];
                arr[pivot-1] = arr[pivot];
                arr[pivot] = arr[i];
                arr[i] = temp;
            }
            pivot--;
        }else {
            i++;
        }
    }
    const left = quickSort(arr.slice(0, pivot));
    const right = quickSort(arr.slice(pivot+1));
    return [...left, arr[pivot], ...right];
}
console.log("quickSort", quickSort([5,2,3,9,1,2,7,3]));

function countingSort(arr, min, max) {
    const countArrLen = max-min+1;
    const countArr = new Array(countArrLen).fill(0);
    for(let i=0;i<arr.length;i++){
        const index = arr[i]-min;
        countArr[index]++;
    }
    for(let i=1;i<countArrLen;i++) {
        countArr[i] += countArr[i-1]
    }
    countArr.pop();
    countArr.unshift(0);
    const resultArr = new Array(arr.length);
    for(let i=0;i<arr.length;i++) {
        const index = countArr[arr[i]-min];
        resultArr[index] = arr[i];
        countArr[arr[i]-min]++;
    }
    return resultArr;
}
console.log("countingSort", countingSort([5,2,3,9,1,2,7,3], 0, 9));