কাউন্টিং সর্ট(Counting Sort)

ডায়নামিক প্রোগ্রামিং সিরিজের এই টিউটোরিয়াল এ শিখব কাউন্টিং সর্ট। কাউন্টিং সর্ট সর্টিং এর খুব সহজ তবে গুরুত্বপূর্ণ একটি অ্যালগরিদম। সর্টিং অ্যালগরিদম গুলোর মাঝে এটি সবথেকে দ্রুত। কারণ, এর Complexity O(n); n হচ্ছে ম্যাক্সিমাম এলিমেন্ট। এখন, আপনার মনে প্রশ্ন আসতে পারে "ডায়নামিক প্রোগ্রামিং এর সাথে কাউন্টিং সর্ট এর কি সম্পর্ক?"। এর উত্তর হচ্ছে, ব্যক্তিগতভাবে আমার মনে হয়, "কাউন্টিং সর্ট এর আইডিয়া হচ্ছে ডায়নামিক প্রোগ্রামিং এর শেকড়"। কারণ, ডায়নামিক প্রোগ্রামিং এর প্রতি ধাপে ধাপেই কাউন্টিং সর্ট এর আইডিয়া ব্যবহৃত হয়। 

একটি অ্যারে সর্ট করার জন্য বিভিন্ন অ্যালগরিদম ব্যবহার করতে পারি, এর মাঝে O(n^2) কমপ্লেক্সিটির সবথেকে জনপ্রিয় অ্যালগরিদম হচ্ছে বাবল সর্ট। এটি অনেকটাই ব্রুট-ফোর্স টেকনিক। আবার O(n log(n)) কমপ্লেক্সিটির আছে কুইক সর্ট অ্যালগরিদম। এটি একটু অপটিমাইজড অ্যালগরিদম। কিন্তু কাউন্টিং সর্ট এর আইডিয়া এদের থেকে একটু ভিন্ন। 

আমাকে একটি অ্যারে {১০ ৫ ৭ ৫ ২} দেওয়া হলো এবং বলা হলো এটি সর্ট করতে হবে। লিমিটেশন হচ্ছে, অ্যারেতে থাকা এলিমেন্ট ১ এর থেকে ছোট এবং ১০০ এর থেকে বড় হবে না। তাহলে আমি একটি আলাদা mark নামের একটি অ্যারে নিতে পারি। আইডিয়া টি হচ্ছে, যেহেতু, এলিমেন্ট ১০০ এর থেকে বড় হবে না সেহেতু, ইনপুট অ্যারে তে প্রথমে যে এলিমেন্ট, ধরে নিলাম ১০ আছে। তাহলে mark অ্যারেতে ১০ নাম্বার ঘরে ১ বসিয়ে দিব। মানে এখন পর্যন্ত ১০ একবার এসেছে, সেটি মার্ক করে রাখলাম। তবে শুরুতে অবশ্যই mark অ্যারের সবগুলো পজিশনে ০ বসিয়ে নিতে হবে। এর পরের এলিমেন্ট ধরে নিলাম ৫। তাহলে mark অ্যারের ৫ নাম্বার ঘরে ১ বসিয়ে দিব। এরপরের এলিমেন্ট ৭। তাহলে mark অ্যারের ৭ নাম্বার ঘরে ১ বসিয়ে দিব। এরপরের এলিমেন্ট আবার ৫। তাহলে ৫ তম ঘরে ২ বসিয়ে দিব। কারণ, ৫ ইতিমধ্যেই ১ বার এসেছে। তাহলে এখন বুঝতে পারব ৫ দুইবার আছে। এরপরের এলিমেন্ট ২। তাহলে mark অ্যারের ২ নাম্বার ঘরে ১ বসিয়ে দিব। 

উপরের চিত্রে বুঝার সুবিধার্থে ১১ সাইজের mark অ্যারে দিয়ে দেখিয়েছি। ১০০ সাইজের নিলে চিত্রে জায়গা হত না। তবে, এ ক্ষেত্রে কিন্তু খুব সাবধান হতে হবে। কারণ, যদি বলা হয় ম্যাক্সিমাম এলিমেন্ট হবে ১০০ আর যদি আমি mark অ্যারে নেই ৫০ সাইজের বা ১০০ এর থেকে ছোট। তাহলে, কিন্তু প্রোগ্রামের মাথা খারাপ হয়ে যাবে। মানে Run Time Error!

মূল কাজ শেষ, এখন শুধু এলিমেন্ট গুলো প্রিন্ট করার পালা। এখন 1 থেকে N (N হচ্ছে সম্ভাব্য ম্যাক্সিমাম এলিমেন্ট) পর্যন্ত লুপ চালিয়ে দেখব mark অ্যারের বর্তমান ঘরে কত আছে। যদি বর্তমান ঘরে ৩ থাকে তাহলে বর্তমান ঘর বা পজিশন টি ৩ বার প্রিন্ট করে দিব। ০ থাকলে ঐ ঘর বা পজিশনের কোন এলিমেন্ট ইনপুট অ্যারেতে নেই। আশাকরছি কোড দেখার আগেই সমাধান লিখে ফেলতে পারবেন।

const int N = 100; int mark[N+1]; void CountingSort(int ar[], int n) {   for (int i = 1;i <= N;i++) {     mark[i] = 0;   }   // count a value to how many times it comes   for (int i = 0;i < n;i++) {     mark[ar[i]]++;   }   for (int i = 1;i <= N;i++) {     // print the value in total     while (mark[i] > 0) {       cout << i << ' ';       mark[i]--;     }   }   cout << endl; }

এই যে একটু টেকনিক খাটিয়ে মার্ক করে সময় অনেক কমিয়ে কাজ টি করে ফেললাম, এই কাজটিকেই ডায়নামিক প্রোগ্রামিং বলতে পারি। যদিও ডায়নামিক প্রোগ্রামিং এর বিস্তৃতি অনেক বড় তবে এটি শিখে থাকলে আপনি ডায়নামিক প্রোগ্রামিং এর মূল এবং অনেক বড় একটি ধাপ অতিক্রম করলেন! 

উল্লেখ্য বিষয় হচ্ছে, এই অ্যালগরিদমের অনেক বড় একটা সীমাবদ্ধতা আছে!!! নিশ্চয়ই খেয়াল করেছেন, ইনপুট লিমিট যদি অনেক বড় হয় তাহলে এই অ্যালগরিদম কাজ করবে না। এটি আসলে ডায়নামিক প্রোগ্রামিং এর ও একটি বড় সীমাবদ্ধতা। আর এই কারণেই সি++ এর STL এর সর্ট ফাংশনে এই অ্যালগরিদম ব্যবহার না করে কুইক সর্ট অ্যালগরিদম ব্যবহার করা হয়েছে। 

প্র্যাক্টিস প্রবলেম।
Spy Detected!
Juggling Letters