Sort

Several classic sorting algorithms.

• Bubble Sort

function bubble(arr, n) {
    for (let i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            let temp = arr[i]
            arr[i] = arr[i + 1]
            arr[i + 1] = temp
        }
    }
}

function bubbleSort(arr) {
    for (let i = arr.length; i > 1; i--) {
        bubble(arr, i)
    }
}

let arr = [9, 8, 7, 6, 5, 4, 3, 2, 1]
bubbleSort(arr)
console.log(arr)

• Selection Sort

function findMaxPosition(arr, n) {
    let pos = 0
    let max = arr[pos]

    for (let i = 0; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i]
            pos = i
        }
    }

    return pos
}

function selectionSort(arr) {
    for (let i = arr.length; i > 1; i--) {
        let pos = findMaxPosition(arr, i)
        let temp = arr[pos]
        arr[pos] = arr[i - 1]
        arr[i - 1] = temp
    }
}

let arr = [0, 3, 4, 5, 7, 9, 8, 10, 1, 2]
selectionSort(arr)
console.log(arr)

• Insert Sort

function insert(arr, n) {
    let pos = n - 1
    let key = arr[pos]

    for (; key < arr[pos - 1] && pos > 0; pos--) {
        arr[pos] = arr[pos - 1]
    }

    arr[pos] = key
}

function insertSort(arr) {
    for (let i = 2; i <= arr.length; i++) {
        insert(arr, i)
    }
}

let arr = [3, 6, 7, 4, 2, 1, 5]
insertSort(arr, arr.length)
console.log(arr)

• Shell Sort

function shellSort(arr) {
    for (let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for (let i = gap; i < arr.length; i++) {
            let pos = i
            let key = arr[pos]
            for (; pos > 0 && arr[pos - gap] > key; pos -= gap) {
                arr[pos] = arr[pos - gap]
            }
            arr[pos] = key
        }
    }
}

let arr = [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 100, 0, -1, 22, 23]
shellSort(arr)
console.log(arr)

• Merge Sort

function merge(arr, l, m, r) {
    let arrL = arr.slice(l, m)
    let arrR = arr.slice(m, r + 1)

    let i = 0
    let j = 0
    let k = l

    for (; i < arrL.length && j < arrR.length; k++) {
        if (arrL[i] < arrR[j]) {
            arr[k] = arrL[i]
            i += 1
        } else {
            arr[k] = arrR[j]
            j += 1
        }
    }

    for (; i < arrL.length; i++ & k++) {
        arr[k] = arrL[i]
    }
    for (; j < arrR.length; j++ & k++) {
        arr[k] = arrR[j]
    }
}

function mergeSort(arr, l, m, r) {
    if (r > l) {
        mergeSort(arr, l, Math.floor((l + m) / 2), m - 1)
        mergeSort(arr, m, Math.floor((m + r + 1) / 2), r)
        merge(arr, l, m, r)
    }
}

let arr = [0, 2, 4, 6, 8, 1, 3, 5, 7, 9, 100, 55]
mergeSort(arr, 0, Math.floor(arr.length / 2), arr.length - 1)
console.log(arr)

• Quick Sort

function partition(arr, l, r) {
    let pivot = arr[r]
    let pos = l

    for (let i = l; i < r; i++) {
        if (arr[i] < pivot) {
            let temp = arr[i]
            arr[i] = arr[pos]
            arr[pos] = temp
            pos += 1
        }
    }

    arr[r] = arr[pos]
    arr[pos] = pivot

    return pos
}

function quickSort(arr, l, r) {
    if (r > l) {
        let pos = partition(arr, l, r)
        quickSort(arr, l, pos - 1)
        quickSort(arr, pos + 1, r)
    }
}

let arr = [9, 3, 8, 1, 2, 100, 5, 4, 0, 6, 7]
quickSort(arr, 0, arr.length - 1)
console.log(arr)

• Heap Sort

function heapify(arr, size, i) {
    let maxIndex = i
    let left = 2 * i + 1
    let right = 2 * i + 2

    if (left < size && arr[left] > arr[maxIndex]) {
        maxIndex = left
    }
    if (right < size && arr[right] > arr[maxIndex]) {
        maxIndex = right
    }

    if (maxIndex !== i) {
        let temp = arr[maxIndex]
        arr[maxIndex] = arr[i]
        arr[i] = temp

        heapify(arr, size, maxIndex)
    }
}

function maxHeap(arr, size) {
    for (let i = Math.floor(size / 2) - 1; i >= 0; i--) {
        heapify(arr, size, i)
    }
}

function heapSort(arr) {
    for (let i = arr.length; i > 1; i--) {
        maxHeap(arr, i)
        let temp = arr[i - 1]
        arr[i - 1] = arr[0]
        arr[0] = temp
    }
}

let arr = [9, 3, 8, 1, 2, 100, 5, 4, 0, 6, 7, 55, 66, 44]
heapSort(arr)
console.log(arr)