เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของตัวเลขและจัดเรียงโดยใช้อัลกอริทึมการเรียงลำดับการนับ
ถ้าเราทราบค่าสูงสุด เราก็สามารถใช้อัลกอริธึมการเรียงลำดับการนับเพื่อจัดเรียงอาร์เรย์ของ Numbers ในเวลาเชิงเส้นและปริภูมิได้ การใช้ค่าสูงสุดจะสร้างอาร์เรย์ที่มีขนาดดังกล่าวเพื่อนับการเกิดขึ้นของค่าดัชนีแต่ละค่า
จากนั้น เราจะแยกดัชนีทั้งหมดที่มีการนับที่ไม่ใช่ศูนย์ในอาร์เรย์ผลลัพธ์ของเรา
ก่อนอื่นเราจะใช้หนึ่งลูปเพื่อค้นหาองค์ประกอบที่ยิ่งใหญ่ที่สุดของอาร์เรย์ เมื่อเราได้แล้ว เราจะใช้การเรียงลำดับการนับเพื่อจัดเรียงอาร์เรย์
ตัวอย่าง
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)); ผลลัพธ์
และผลลัพธ์ในคอนโซลจะเป็น −
[ 1, 2, 3, 3, 4 ]
