কাউন্টিং সর্ট এলগরিদম – সবচেয়ে সহজ সর্টিং অ্যালগরিদম

Post updated on 29th January, 2020 at 08:13 am

একটা প্রবলেমের কথা চিন্তা করা যাক!

তোমাকে বাংলাদেশের ১৬ কোটি মানুষের বয়স ইনপুট দেয়া হবে। নানান বয়সী মানুষের বয়স নিয়ে তোমাকে কাজ করতে হবে। কেউ হয়ত একদম ল্যাদা বাচ্চা, আবার কেউ হয়ত তোমার দাদা-নানার বয়সী। ইনপুট দেয়ার পর ধর তোমাকে সবগুলো মানুষের বয়সকে ছোট থেকে বড় আকারে সাজাতে হবে। এরপর প্রথম থেকে প্রিন্ট করতে হবে বা অন্য যে কোন অপারেশন চালাতে হবে।

• বাবল সর্ট অ্যালগরিদম – Bubble Sort Algorithm

তোমরা যারা এতদিনে প্রোগ্রামিং এ অনেকখানি এগিয়ে গেছ তারা Bubble Sort এর ব্যাপারটা জেনে থাকবে। তো প্রথমেই যেটা মাথায় মাথায় আসবে যে একটা int array নিব 16,00,00,000 সাইজের। এরপর একেকজন আদমীর বয়স ইনপুট নিব আর array তে ঢুকায় দিতে থাকব। কোন এক সময় এই ইনপুট নেয়ার কর্মযজ্ঞ শেষ হলে বাবল সর্ট এলগরিদমের মাধ্যমে ধুপ-ধাপ সর্ট করে প্রিন্ট করে ফেলব! কাজ খতম!

কাজ খতম করার উদ্দেশ্যে কোড লিখা শুরু করলা নিচের মত করেঃ

int arr[160000000];

for(int i = 0; i<160000000; i++)
{
    scanf("%d", &arr[i]);
}

বিপত্তি বাধলো কোড রান করতে গিয়ে। দেখলে এত বড় অ্যারে ডিক্লেয়ার করা যায় না। প্রোগ্রাম ক্র্যাশ করে। তাহলে উপায়?

উপায় বাতলে দেবার জন্যেই কাউন্টিং সর্ট অ্যালগরিদম (Counting Sort Algorithm). এই অ্যালগরিদমের সাহায্যে মাত্র ২০০ সাইজের একটা অ্যারে ডিক্লেয়ার করেই এই প্রবলেমটা সলভ করা যায়।

স্বাভাবিক ভাবেই একজন মানুষ বর্তমানে ১০০ বছরের বেশি বাঁচে না। তাও ধরে নিলাম মানুষের সর্বোচ্চ বয়স হতে পারে ২০০ বছর! চিন্তা করে দেখ, বাংলাদেশের এই ১৬ কোটি মানুষের প্রত্যেকের বয়সই কিন্তু এই রেঞ্জের মধ্যে রয়েছে। আমরা কিন্তু একটা কাজ করতে পারি! কোন বয়সের মানুষ কতজন আছে সেটা হিসাব করলেই কিন্তু সব বয়সের মানুষের বয়স ছোট থেকে বড় আকারে সাজানো যায়। ধর 15 জন মানুষের বয়সের এই লিস্টটা ইনপুট করা হলঃ

INPUT: 3 2 3 1 5 3 2 5 1 2 5 1 3 2 2

আমরা গুণে ফেলতে পারি কোন বয়সী লোকের সংখ্যা কত। তাহলে হিসাবটা দাঁড়ায়ঃ

1 বছর বয়সী মানুষ = 3 জন
2 বছর বয়সী মানুষ = 5 জন
3 বছর বয়সী মানুষ = 4 জন
4 বছর বয়সী মানুষ = 0 জন
5 বছর বয়সী মানুষ = 3 জন

এখন আমাদেরকে সবার বয়স ছোট থেকে বড় ক্রমে প্রিন্ট করতে বলা হলে আমরা ১ প্রিন্ট করব ৩ বার, ২ প্রিন্ট করব ৫ বার, ৩ প্রিন্ট করব ৪ বার, ৪ প্রিন্ট করব ০ বার এবং ৫ প্রিন্ট করব ৩ বার। লক্ষ্য কর, ইনপুটের লিস্টটার সাইজ ১৫, কিন্তু বয়সের রেঞ্জ ৫ পর্যন্ত হওয়ায় ৫টা ভ্যারিয়েবলের মাধ্যমেই ১৫ জনের বয়সের হিসাব রাখা গেছে। এটাই কাউন্টিং সর্ট এলগদিরদম।

কোড দেখার আগে Counting Sort Algorithm এর illustration-টা দেখে নিতে পারো এখান থেকে।

এবার কোডটা দেখিঃ

//বয়সের রেঞ্জ ধরা হয়েছে ১ থেকে ৫। ধরা যাক এই অ্যারের সব ইন্ডেক্সের মান শুরুতে শূণ্য 
int arr[6]; 

for(int i = 1; i<=15; i++) 
{ 
    scanf("%d", &age); 
    arr[age] = arr[age] + 1; 
}

এই কোডব্লকই কাউন্টিং সর্ট এর জন্য কাজ করে। Loop এর মাধ্যমে ১৫ জনের বয়স ইনপুট নেয়া হচ্ছে। প্রতিবার age নামক int type variable এ বয়স ইনপুট নেয়া হচ্ছে। পরের লাইনেই arr অ্যারের age-তম ইন্ডেক্সের মান ১ করে বাড়িয়ে দেয়া হচ্ছে। আমাদের হাতে থাকা বয়সের লিস্ট অনুযায়ী একদম শুরুতে ইনপুট দেয়া হয়েছিল 3. এটা ইনপুট হবার পর ৬ নাম্বার লাইনে arr[3] = arr[3] + 1 করা হয়েছে। যার ফলে arr[3] ইন্ডেক্সের মান হল ১। কারণ array এর সব ইন্ডেক্স এর মান শুরুতে zero ছিল। এরপর 2 ইনপুট করা হয়েছে। ৬ নাম্বার লাইনে এবার ঘটবে arr[2] = arr[2] + 1. অর্থাৎ arr[2] এর মান হল 1. তৃতীয় সংখ্যাটা 3. ৬ নাম্বার লাইনের কাজ হবে arr[3] = arr[3] + 1; উল্লেখ্য arr[3] এর মান কিন্তু প্রথম ইনপুট নেয়ার সময়ই ১ হয়ে গেছে। তাহলে এখন arr[3] এর মান হবে 2. এভাবে করে ১৫ টা বয়স ইনপুট নিয়ে সেরেফ তাদের frequency calculate করা হয়েছে।

এখন যদি সকলের বয়স ছোট থেকে বড় আকারে প্রিন্ট করতে বলা হয় তাহলে নিচের কোড লেখা যেতে পারেঃ

for(int i = 1; i<=5; i++)
{
    if(arr[i]>0)
    {
        for(int j = 1; j<=arr[i]; j++)
            printf("%d ", i);
    }

}

এখানে i এর মান হচ্ছে বয়স। অ্যারের i-তম ইন্ডেক্সের মান শূণ্যের চেয়ে বড় হলে অর্থাৎ এই বয়সের মানুষের সংখ্যা শূণ্যের চেয়ে বড় হলে দ্বিতীয় লুপের মাধ্যমে arr[i] সংখ্যক বার i এর মান প্রিন্ট করা হচ্ছে।

এখন যদি বলা হয় কোন বয়সের মানুষের সংখ্যা কত তাহলে ৫ বার লুপ ঘুরিয়েই এটা বলে দেয়া যায়ঃ

for(int i = 1; i<=5; i++)
{
   printf("%d ", arr[i]);
}

মোদ্দা কথা হচ্ছে আমাদের ইনপুট সেট যদি নির্দিষ্ট রেঞ্জের মধ্যে হয়, যেই রেঞ্জের অ্যারে ডিক্লেয়ার করা সম্ভব আর এরকম ফ্রিকোয়েন্সি হিসাব করে সমাধান করা যায় তাহলে এসব ক্ষেত্রে কাউন্টিং সর্ট অ্যালগরিদম সবচেয়ে ভাল কাজ করে। Counting Sort Algorithm এর time complexity হচ্ছে O(n). যেখানে, n = number of input data.

পুরো কোডটা পাওয়া যাবে গিটহাব রিপোজিটরিতে।

এই সর্টিং এলগরিদম ব্যবহার করে সলভ করতে পারো UVa 11462 – Age Sort প্রবলেমটি।