জাভাস্ক্রিপ্টে কাউন্টিং সর্ট ইমপ্লিমেন্টেশন

সমস্যা বিবরণ

নাম্বার অ্যারে দেওয়া আছে। কাউন্টিং সর্ট অ্যালগরিদম ব্যবহার করে সর্ট করতে হবে। যদি ম্যাক্সিমাম ভ্যালু জানা থাকে, O(n) টাইমে সর্ট করা যায়।

সমাধান

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]

আউটপুট

[ 1, 2, 3, 3, 4 ]

ব্যাখ্যা

• findMaximum: O(n) এ ম্যাক্স বের করা।
• counts অ্যারে: ইনডেক্স = নম্বর, ভ্যালু = ফ্রিকোয়েন্সি।
• দ্বিতীয় লুপে counts ট্রাভার্স করে সর্টেড অ্যারে বানানো।
• কমপ্লেক্সিটি: O(n + k) যেখানে k = ম্যাক্স ভ্যালু।

সীমাবদ্ধতা

শুধু নন-নেগেটিভ ইন্টিজার এবং ছোট রেঞ্জের জন্য উপযোগী। বড় রেঞ্জ বা নেগেটিভ নম্বরের জন্য উপযুক্ত নয়।