পোস্টটি পড়া হয়েছে 13,254 বার
কাউন্টিং সর্ট counting sort algorithm

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

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

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

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

তোমরা যারা এতদিনে প্রোগ্রামিং এ অনেকখানি এগিয়ে গেছ তারা 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 প্রবলেমটি।

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

  1. I can’t make any comment in Bangla! What a big problem!! Whatever I try to comment in Bangla, it shows me this error message: “ERROR: Your comment appears to be spam.”

    Anyway, ami mone hoy majkhane ektu jot pakiye felechi! Proti index a kivabe eki songkhar age gulo rakha hocche thik clear hote parchina.
    Ei problem er puro code ta ki Github e deya ache? Purota eksathe dekhle bujhte subidha hote pare.

    1. এখন একটু বাংলায় কমেন্ট করার ট্রাই করে দেখতে পারেন। আমি ২ জায়গা থেকে দেখলাম কমেন্ট করা যাচ্ছে।

      1. ভাইয়া আপনি অ্যারে এর দৈর্ঘ্য দিয়েছেন ৫ ।
        অর্থাৎ এর ইনডেক্স গুলো হবে , ০-৪ পর্যন্ত ।
        আর বয়স সীমা ৫ ।
        তাহলে আমি যখন বয়স ৫ লিখতে যাবো , তখন কোন ইনডেক্স এ আমার ভ্যালু স্টোর হবে ?

        1. অ্যারের সাইজ এই উদাহরণের জন্য অন্তত ৬ নিতে হবে। আমার উদাহরণে দেখানো কোডে ভুল ছিল। এখন ঠিক করে দিয়েছি। অসংখ্য ধন্যবাদ ভুলটা ধরিয়ে দেয়ার জন্য।

  2. ভাইয়া, Nested Loop দিয়ে Sorted value গুলোর যে print দেখানো হয়েছে সেই কোড টুকু কাজ করছে না। Infinity Loop এর কাজ করছে।কেন হচ্ছে বুঝতে পারছি না। আর গিটহাব এ আপনার দেয়া Code এ ও এই Print অংশ টা দেখানো হয়নি।
    আশা করি সমস্যাটা বুঝাতে পেরেছি?

  3. ধন্যবাদ ভাই,কাউন্টিং সর্ট সম্পর্কে এরকম সাজানো গুছানো 1টা পোস্ট করার জন্য ।আপনার পোস্টটা প্রথমবার পরে বুঝতে পারছি ।??

    1. একদম শেষ ব্লকের কোডের কমপ্লেক্সিটি O(n) বলা হয়েছে। সেখানে নেস্টেড লুপ ব্যবহার করা হয় নি।

Leave a Reply

Your email address will not be published. Required fields are marked *