cs-test.js

class CountingSort {
    /**
     * @param A {Number[]|String[]}
     * @param k {Number}
     */
    static sortIntuitiveVerbose(A, k) {
        // console.log(`A=${DTHelper.asPrettyString(A)}`);
        // console.log(`Starting CountingSort - intuitive version: n=${A.length}, k=${k}`);

        // let indices = new Array(k + 1);
        // for (let i = 0; i <= k; i++) indices[i] = i;
        // console.log(`  ${DTHelper.asPrettyString(indices, { brackets: false, comma: false })}`);

        // let arrayR = 0;
        // let arrayW = 0;
        let C = new Array(k + 1).fill(0);
        // arrayW += C.length;
        // console.log(
        //     `C=${DTHelper.asPrettyString(C)}\t${arrayR + arrayW} OPS (${arrayR}xR + ${arrayW}xW)\t-- Done initialising`
        // );

        for (let i = 0; i < A.length; i++) {
            C[A[i]]++;
            // arrayR++;
            // arrayW++;
        }
        // console.log(
        //     `C=${DTHelper.asPrettyString(C)}\t${arrayR + arrayW} OPS (${arrayR}xR + ${arrayW}xW)\t-- Done counting`
        // );

        let pos = 0;
        for (let i = 0; i < C.length; i++) {
            while (C[i] > 0) {
                // arrayR++;
                A[pos++] = i;
                // arrayW++;
                C[i]--;
                // arrayW++;
                // console.log(
                //     `C=${DTHelper.asPrettyString(C)}\t${
                //         arrayR + arrayW
                //     } OPS (${arrayR}xR + ${arrayW}xW)\t-- ${i} >> A[${pos - 1}] : ${DTHelper.asPrettyString(A)}`
                // );
            }
        }

        // console.log(`A=${DTHelper.asPrettyString(A)}`);
        // console.log(
        //     `Done sorting. n=${A.length}, k=${k}. ArrayOperations: ${arrayR + arrayW} (${arrayR}xR + ${arrayW}xW)`
        // );
    }

    /**
     * Original Version
     * @param A {Number[]}
     * @param B {Number[]}
     * @param k {Number}
     */
    static sortVerbose(A, B, k) {
        // console.log(`A=${DTHelper.asPrettyString(A)}`);
        // console.log(`Starting CountingSort - book version: n=${A.length - 1}, k=${k}`);

        // let indices = new Array(k + 1);
        // for (let i = 0; i <= k; i++) indices[i] = i;
        // console.log(`  ${DTHelper.asPrettyString(indices, { brackets: false, comma: false })}`);

        // let arrayR = 0;
        // let arrayW = 0;
        let C = new Array(k + 1);
        for (let i = 0; i <= k; i++) {
            C[i] = 0;
            // arrayW++;
        }
        // console.log(
        //     `C=${DTHelper.asPrettyString(C)}\t${arrayR + arrayW} OPS (${arrayR}xR + ${arrayW}xW)\t-- Done initialising`
        // );

        for (let j = 1; j < A.length; j++) {
            C[A[j]]++;
            // arrayR++;
            // arrayW++;
        }
        // console.log(
        //     `C=${DTHelper.asPrettyString(C)}\t${arrayR + arrayW} OPS (${arrayR}xR + ${arrayW}xW)\t-- Done counting`
        // );

        for (let i = 1; i <= k; i++) {
            C[i] += C[i - 1];
            // arrayR++;
            // arrayW++;
        }
        // console.log(
        //     `C=${DTHelper.asPrettyString(C)}\t${
        //         arrayR + arrayW
        //     } OPS (${arrayR}xR + ${arrayW}xW)\t-- Done adding neighbours`
        // );

        for (let j = A.length - 1; j >= 1; j--) {
            let item = A[j];
            // arrayR++;
            let pos = C[item];
            // arrayR++;
            B[pos] = item;
            // arrayW++;
            C[item]--;
            // arrayW++;
            // console.log(
            //     `C=${DTHelper.asPrettyString(C)}\t${
            //         arrayR + arrayW
            //     } OPS (${arrayR}xR + ${arrayW}xW)\t-- ${item} >> B[${pos}] : ${DTHelper.asPrettyString(B)}`
            // );
        }

        // console.log(`B=${DTHelper.asPrettyString(B)}`);
        // console.log(
        //     `Done sorting. n=${B.length - 1}, k=${k}. ArrayOperations: ${arrayR + arrayW} (${arrayR}xR + ${arrayW}xW)`
        // );
    }
}



function testCountingSort() {
    let values = [99999999, 99999998, 99999997, 99999996, 99999995, 99999994, 99999993, 99999992] ;
    let sortedValues = Array.from(values);
    let at = Date.now();
    CountingSort.sortIntuitiveVerbose(sortedValues, 99999999);
    console.log(Date.now() - at);

    let bookValues = [null, 99999999, 99999998, 99999997, 99999996, 99999995, 99999994, 99999993, 99999992] ;
    let sortedBookValues = new Array(bookValues.length).fill(null);
    let bt = Date.now();
    CountingSort.sortVerbose(bookValues, sortedBookValues, 99999999);
    console.log(Date.now() - bt);
}
testCountingSort();