Arkar Myat

Javascript Sorting Algorithms

Apr 24, 2023Arkar
Javascript

Some of the javascript sorting algorithms that I stumble upon.

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

function bubbleSort(arr: number[]){
   let swapped = false;
   for(let i =0; i < arr.length; i ++) {
       for(let j = 0 ; j < arr.length - 1 - i ; j++){
           if(arr[j] > arr[j + 1]){
               let tmp = arr[j]
               arr[j] = arr[j + 1]
               arr[j + 1] = tmp
               swapped = true 
           }
       }
       if(!swapped){
           return arr
       }
   }
}

function merge(left : number[],right:number[]){
    let res = []
    while(left.length && right.length){
        if(left[0] < right[0]) {
            res.push(left.shift())
        }else{
            res.push(right.shift())
        }
    }
    return res.concat(left,right)
}

function mergeSort(arr:number[]){
    if(arr.length < 2) return arr
    let mid = Math.floor(arr.length / 2)
    let leftArr = arr.slice(0, mid)
    let rightArr = arr.slice(mid)
    let sortedLeft = mergeSort(leftArr)
    let sortedRight = mergeSort(rightArr)
    return merge(sortedLeft,sortedRight)
}

function quickSort(arr:number[]){
    if(arr.length < 2) return arr
    let length = arr.length
    let pivot = arr[length - 1]
    let leftArr = []
    let rightArr = []
    for(let i = 0; i < length - 1; i ++ ){
        if(arr[i] < pivot){
            leftArr.push(arr[i])
        }else {
            rightArr.push(arr[i])
        }
    }
    let sortedLeft = quickSort(leftArr)
    let sortedRight = quickSort(rightArr)
    return sortedLeft.concat(pivot,sortedRight)
}