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

Dec 6, 2013

আগের পর্বঃ বাবল সর্ট

সর্টিং এর জন্য যে সকল এলগোরিদম আছে তার মধ্যে সবচেয়ে এফিসিয়েন্ট হল কাউন্টিং সর্ট। এটি O(n) টাইম কমপ্লেক্সিটিতে কাজ করে! কেবল এফিসিয়েন্টই না, একই সাথে অত্যন্ত সহজও। আসলে একে আলাদা কোন এলগোরিদম না বললেও চলে। খুবই সাধারণ ধারণা দিয়েই কাজটি করে ফেলা যায়।

ধরা যাক আমাদেরকে কিছু নাম্বার দেওয়া হল যেগুলোকে সর্ট করতে হবে। নাম্বারগুলো হল,
5, 2, 1, 3, 6, 4, 7, 8, 9, 5, 10, 11, 12, 5, 6, 8, 13, 10, 9, 7

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

কাউন্টিং সর্টের মূল কনসেপ্টটা হল যে নাম্বার ইনপুট দেওয়া হবে, তাকে কোন অ্যারেতে না রেখে বরং অ্যারের ঐ ইন্ডেক্সের ভেলু আমরা এক বাড়িয়ে দিব! ধরা যাক আমাদেরকে বলা আছে যে নাম্বারগুলো 0 থেকে 15 এর মধ্যে আছে। তাহলে আমরা প্রথমে একটা অ্যারে ডিক্লেয়ার করব,

#define MAX 15
int ara[MAX];

আমরা অ্যারেটা গ্লোবালি ডিক্লেয়ার করব অথবা memset() ব্যবহার করে অ্যারের প্রতিটা এলিমেন্টকে 0 বানিয়ে নিব। এবার উপরের নাম্বারগুলো দেখা যাক। একটা করে নাম্বার ইনপুট নিব আর ঐ ইন্ডেক্সের মান এক করে বাড়িয়ে দিব অর্থাৎ += 1 বা ++ করে দিব।

int x;
while( scanf( "%d", &x ) == 1 ) {
    ara[x]++;    // x-তম ইন্ডেক্সের ভেলু এক বাড়িয়ে দিলাম
}

এই প্রক্রিয়াটি যখন চলবে তখন প্রথমে ইনপুট আসবে 5। ara[5]++ হয়ে ara[5] = 1 হবে। এরপর 2 আসলে ara[2]++ হবে। এভাবে প্রতিটা নাম্বার আসবে এবং তার ইন্ডেক্সের ভেলু বাড়তে থাকবে। দ্বিতীয়বার যখন 5 আসবে তখন ara[5]++ হয়ে ara[5] = 2 হবে। তৃতীয়বার 5 আসলে ara[5] = 3 হবে। অর্থাৎ একটা নাম্বার যতবার পাবে, তার ইন্ডেক্সের ভেলু তত হবে। যদি না পায় তাহলে শুরুতে 0 ছিল, ঐটাই থেকে যাবে। এভাবে আমরা পুরো কাজটা শেষে কোন নাম্বার কতবার আসলো সেটা ঐ ইন্ডেক্সের ভেলু থেকে সহজেই পেয়ে যাচ্ছি।

উপরের ইনপুটগুলো যদি নেওয়া হবে এবং এই কাজটি করা হলে অ্যারেটি কেমন হবে দেখা যাক,

index    x     0  1  2  3  4  5  6  7  8  9  10  11  12  13  14
value  ara[x]  0  1  1  1  1  3  2  2  2  2   2   1   1   1   0

একটু চিন্তা করলেই বোঝা যাবে যে আমরা আমাদের নাম্বারগুলোকে সর্ট করে ফেলেছি। কিভাবে? আমরা নাম্বারগুলো যতবার আছে তার ইন্ডেক্সে সেই ভেলু রেখে দিয়েছি। ইন্ডেক্সগুলো তো আগে থেকেই সর্টেড! এখন আমরা যদি অ্যারের শুরু থেকে শেষ পর্যন্ত একটা লুপ চালাই এবং প্রতিটা নাম্বার যতবার করে পেয়েছি ততবার করে প্রিন্ট করি তাহলেই নাম্বারগুলো সর্টেড হয়ে প্রিন্ট হবে!

for( int i = 0; i < MAX; i++ ) {
    for( int j = 0; j < ara[i]; j++ ) {
        printf( "%d ", i );
    }
}

Output:
1 2 3 4 5 5 5 6 6 7 7 8 8 9 9 10 10 11 12 13

হয়ে গেল সর্টিং! এতোটাই সহজ!

এখন প্রশ্ন আসে, কাজটা যখন এতোই সহজ, আর এতোই এফিসিয়েন্ট, তাহলে আমরা সবসময় এটা কেন ব্যবহার করি না? কিছু চিন্তা না করেই বলে দেওয়া যায় যেহেতু কাজটা অনেক সহজ, অতএব এর অনেক বাধা-বিপত্তি আছে। :P

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

আবার যদি ঋণাত্মক নাম্বার ইনপুটে থাকে, তাহলে আরেক সমস্যা। অ্যারের ইন্ডেক্স তো ঋণাত্মক হতে পারে না। তখন এই প্রক্রিয়ায় কাজ করা অনেক সমস্যা হয়ে যাবে। ম্যাপিং করে অনেক ঝামেলা করতে হবে। অর্থাৎ সহজ ভাষায় ইনপুটে যদি 2^30 বা -59 এই ধরণের নাম্বার থাকে সেক্ষেত্রে কাউন্টিং সর্ট দিয়ে কাজ করা যাবে না। (ঋণাত্মক নাম্বারের ক্ষেত্রে করা যাবে, কিন্তু অনেক ঝামেলা করতে হবে!)

আবার যদি এমন হয়, আমাদেরকে ইনপুট দেওয়া হবে 5 টা নাম্বার যাদেরকে সর্ট করতে হবে। নাম্বারগুলো এরকম, 3 2 8 5 9999999। এক্ষেত্রে যদি আমরা কাউন্টিং সর্ট ব্যবহার করি, তাহলে আমাদের লুপ 0 থেকে 9999999 পর্যন্ত চলবে, অর্থাৎ মাত্র 5 টি এলিমেন্টের জন্য 10^8 টি ইটারেশন হবে! সাদা চোখেই দেখা যাচ্ছে 5 টা এলিমেন্টের জন্য বাবল সর্ট অনেক বেশি এফিসিয়েন্ট হবে, কারণ মাত্র 5^2 বা 25 টা ইটারেশনে সর্ট হয়ে যাবে। এখানে ম্যাক্সিমাম এবং মিনিমাম ভেলুর ডিফারেন্স মোট এলিমেন্ট সংখ্যার চেয়ে অনেক বেশি হওয়ায় এমনটি হচ্ছে।

তাহলে যেসব বিষয় মাথায় রাখতে হবে সেগুলো হলঃ

১) নাম্বারগুলোর মিনিমাম এবং ম্যাক্সিমাম ভেলু কত ২) ঋণাত্মক নাম্বার আছে কিনা
৩) ম্যাক্সিমাম ভেলু পর্যন্ত সাইজের অ্যারে ডিক্লেয়ার করা যাবে কিনা
৪) ম্যাক্সিমাম এবং মিনিমাম ভেলুর মধ্যে ডিফারেন্সের সাথে মোট এলিমেন্ট সংখ্যার তুলনা

সহজ কথায় কখন আমরা কাউন্টিং সর্ট ব্যবহার করব এই প্রশ্নের উত্তর হল, যখন মোট এলিমেন্ট সংখ্যা অনেক বেশি থাকবে (যেমন 2^30) কিন্তু নাম্বারগুলোর মধ্যে ম্যাক্সিমাম এবং মিনিমামের ব্যবধান সেই তুলনায় অনেক কম থাকবে (যেমন ম্যাক্সিমাম 200 মিনিমাম 0) তখন আমরা এটি ব্যবহার করব।

প্র্যাকটিস প্রবলেমঃ
১। UVa 11462 - Age Sort