HackerRank Js-Week2 5. Counting Sort 1

    AllenLi
    HackerRank

    Comparison Sorting
    Quicksort usually has a running time of n x log(n), but is there an algorithm that can sort even faster? In general, this is not possible. Most sorting algorithms are comparison sorts, i.e. they sort a list just by comparing the elements to one another. A comparison sort algorithm cannot beat n x log(n) (worst-case) running time, since n x log(n) represents the minimum number of comparisons needed to know where to place each element. For more details, you can see these notes (PDF).

    比較排序：
快速排序的時間複雜度為 n x log(n)，但是有沒有一種演算法可以比排序更快呢？一般來說，這是不可能的。大多數排序演算法都是比較排序，也就是他們通過將元素互相比較來對列表進行排序。
比較排序演算法無法擊敗他的 n x log(n) 運行時間，因為 n x log(n)表示知道將每個元素放在對應的位置所需要的最小比較次數。相關的細節，你可以查看官網的 PDF。

    Alternative Sorting
    Another sorting method, the counting sort, does not require comparison. Instead, you create an integer array whose index range covers the entire range of values in your array to sort. Each time a value occurs in the original array, you increment the counter at that index. At the end, run through your counting array, printing the value of each non-zero valued index that number of times.

    替換排序：
另一個替換排序法，計數排序，不需要比較。相之，你需要建立一個整數的陣列，他的元素位置範圍涵蓋陣列中要排序的數值範圍。每一次原始陣列出現一個數值時，你都會在該元素位置紀錄增加次數。最後，遍歷你的計數陣列，
印出每個非零元素位置的次數。

    Example 1:

    arr = [1,1,3,2,1]
All of the values are in the range [0...3], so create an array of zeros, result = [0,0,0,0]. The results of each iteration follow:
i	arr[i]	result
0	1	[0, 1, 0, 0]
1	1	[0, 2, 0, 0]
2	3	[0, 2, 0, 1]
3	2	[0, 2, 1, 1]
4	1	[0, 3, 1, 1]

The frequency array is [0,3,1,1]. These values can be used to create the sorted array as well: sorted = [1,1,1,2,3].

Constraints
100 <=n <= 10^6
0 <= arr[i] < 100

    solution:
    這題要先注意題目給予的陣列範圍，也就是規格給定的陣列元素有幾個，
    先運用 new Array(100).fill(0) 建立陣列中 100 個元素，並給予對應的值 0。
    接著運用 for 迴圈遍歷 input 的數值，如符合則在陣列對應的元素位置做 +1 的動作。
    最後，回傳這個計算頻率次數的陣列。

    Code 1: BigO(n)

    'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'countingSort' function below.
 *
 * The function is expected to return an INTEGER_ARRAY.
 * The function accepts INTEGER_ARRAY arr as parameter.
 */

function countingSort(arr) {
    // Write your code here
    let frequencyArray = new Array(100).fill(0);
    for (let num of arr){
        frequencyArray[num]++
    }
    return frequencyArray;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const n = parseInt(readLine().trim(), 10);

    const arr = readLine().replace(/\s+$/g, '').split(' ').map(arrTemp => parseInt(arrTemp, 10));

    const result = countingSort(arr);

    ws.write(result.join(' ') + '\n');

    ws.end();
}

    FlowChart:
    Example 1

    arr = [1,1,3,2,1]
frequencyArray = new Array(100).fill(0) //[0,0,0,0,....,0,0]

[0,1,2,3...98,99]

1 [0,1,0,0...0,0]
1 [0,2,0,0...0,0]
3 [0,2,0,1...0,0]
2 [0,2,1,1...0,0]
1 [0,3,1,1...0,0]

    Related Posts