Triển khai Counting Sort trong JavaScript

Cần viết hàm JavaScript nhận mảng số và sắp xếp bằng thuật toán Counting Sort.

Nếu biết giá trị tối đa, có thể dùng Counting Sort để sắp xếp mảng số trong thời gian và không gian tuyến tính. Dùng giá trị tối đa tạo mảng kích thước đó để đếm số lần xuất hiện của mỗi giá trị chỉ số.

Sau đó, trích xuất tất cả chỉ số có số đếm khác 0 vào mảng kết quả.

Đầu tiên dùng một vòng lặp tìm phần tử lớn nhất của mảng, sau đó dùng Counting Sort để sắp xếp.

Ví dụ

const arr = [4, 3, 1, 2, 3]; 
const findMaximum = arr => arr.reduce((acc, val) => val > acc ? val: acc, Number.MIN_VALUE) 
const countingSort = (arr = []) => { 
    const max = findMaximum(arr); 
    const counts = new Array(max + 1); 
    counts.fill(0); 
    arr.forEach(value => counts[value]++); 
    const res = []; 
    let resultIndex = 0; 
    counts.forEach((count, index) => { 
        for (let i = 0; i < count; i++) { 
            res[resultIndex] = index; 
            resultIndex++; 
        }; 
    }); 
    return res; 
}; 
console.log(countingSort(arr));

Kết quả

Kết quả trong console sẽ là:

[ 1, 2, 3, 3, 4 ]