นำ Counting Sort มาใช้ใน JavaScript

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของตัวเลขและจัดเรียงมันโดยใช้อัลกอริทึม counting sort หากเรารู้ค่าสูงสุด เราสามารถใช้อัลกอริทึม counting sort เพื่อจัดเรียงอาร์เรย์ของตัวเลขในเวลาและพื้นที่เชิงเส้น (linear) โดยใช้ค่าสูงสุดสร้างอาร์เรย์ขนาดนั้นเพื่อนับจำนวนครั้งของแต่ละค่าดัชนี จากนั้นเราจะดึงดัชนีทั้งหมดที่มีจำนวนนับไม่เป็นศูนย์เข้าไปในอาร์เรย์ผลลัพธ์ เราจะใช้ลูปหนึ่งรอบเพื่อหาสมาชิกที่มากที่สุดของอาร์เรย์ ก่อนหน้านั้น เมื่อเรามันแล้ว เราจะใช้ counting sort เพื่อจัดเรียงอาร์เรย์

ตัวอย่าง

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 ]