বাবল সর্ট কি ????

যারা কম বেশি প্রোগ্রামিং করেন বা জানেন তাদের কম বেশি সবারই সর্টিং নিয়ে কাজ করার অভিজ্ঞতা আছে। এই সর্টিং সমস্যা সমাধানের একটি উপায় হল বাবল সর্ট এলগোরিদম।এলগোরিদমের বিশাল রাজ্যে সব থেকে সহজ একটি এলগো ।

কিভাবে কাজ করে????

ধরুন আপনাকে 3টি সংখ্যার একটা সেট দেওয়া হল। উদাহরণস্বরুপ ধরে নিলাম A=[4,2,3,1]।এর পর আপনাকে বলা হল এই সেটটিকে ছোট থেকে বড় আকারে সাজাও।

আপনি এর পর কি করবেন ?

আপনি প্রথমে যে কাজটি করবেন তা হলে এই 3টি সংখ্যার মধ্যে কোনটি ছোট তা খুঁজবেন তারপর এর থেকে বড় ।এর পর তার থেকেও বড়। এইভাবে আপনি আপনার সেটটি সাজাবেন। ঠিক না ? হুম আসলেই এই রকম । কিন্তু আপনি কি লক্ষ্য করছিলেন আপনি ছোট সংখ্যাটি খোঁজার সময় ওই সংখ্যাটিকে আশেপাশে অন্য সংখ্যার সাথে তুলনা করছিলেন ? হা আপনি আপনি তুলনা করে যে সংখ্যাটিকে আপনার সবার থেকে ছোট মনে হয়েছে আপনি সেইটাই প্রথমে লিখেছেন। তাই নয় কি ?

বাবল সর্টও এইভাবে কাজ করে । সে প্রথমে সম্ভাব্য সব থেকে ছোট সংখ্যা কে 0 তম ইনডেক্সে রাখে এর পর আরেকটাকে । তারপর আরেকটা………। আর এই জন্য সে প্রতিটি এলিমেন্টকে তার নিকটতম এলিমেন্টের সাথে তুলনা করে। তারপর যে এলিমেন্টটি বড় হয় সেই এলিমেন্টটি পরবর্তী ইনডেক্সের সাথে সোয়াপ করে। মানে হল জায়গা পরিবর্তন করে। আর এইভাবে সে N পর্যন্ত চলতে থাকে। এইবার আমরা আমদের সেই উদাহরণে ফিরে যায়ঃ

4,2,3,1 এই 3টি সংখ্যাকে আমরা বাবল সর্ট করলে কেমন হবে? প্রথমে আমরা 0 এবং 1 নাম্বার ইনডেক্সের মধ্যে তুলনা করব কোনটি বড়। তাহলে দাঁড়ায়ঃ

2,4,3,1

এর পর 1 নাম্বার ইনডেক্সের সাথে 2 নাম্বার ইনডেক্সের তুলনা করি।

2,3,4,1

এর পর ২ এর সাথে ৩।

2,3,1,4

আমার প্রথম স্টেপের কাজ শেষ। এইবার দ্বিতীয় স্টেপ শুরু হবে। আবার 0 থেকে 1, 1 থেকে 2, 2 থেকে 3।

2,1,3,4

এইখানে লক্ষ্য করুন শেষ 2 ধাপে অবস্থার কোন পরবর্তন হয়নি । এর কারণ হল 1,3,4 অলরেডি তাদের পারফেক্ট পজিশন পেয়ে গিয়েছে।

এই বার আমরা আমাদের তৃতীয় স্টেপের কাজ শুরু করব। দেখা যাক কি দাঁড়ায়ঃ

1,2,3,4

ওয়াও মনে হচ্ছে আমরা আমাদের কাঙ্খিত উত্তর পেয়ে গিয়েছি । 😀

লক্ষ্য করুনঃ আমাদের পুরো কাজটি শেষ করতে কতটি ধাপ লেগেছে ? হ্যা ঠিকই। আমাদের ধাপ সংখ্যা হল n-1। অথার্থ আমাদের লুপটিকে n-1 পর্যন্ত ঘুরাতে হবে।আবার দেখুন ওই লুপের ভিতর আবার আমরা 3টি করে স্টেপ করেছি না ? তার মানে কি দাঁড়াল ? আমাদের আরেকটি ইনার লুপ লাগবে যার ধাপ সংখ্যাও n-1।

তাহলে আমাদের বেসিক সুডো কোড দাঁড়াল এই রকমঃ

  
    for(j=0;j<n-1;j++){  
        for(i= 0;i<n-1;i++){  
            if(Num[i]>num[i+1]){  
                Int temp= num[i];  
                Num[i]= num[i+1];  
                Num[i+1]= temp;  
            }  
        }  
    }

হ্যা আমাদের বাবল সর্ট শিখা শেষ। এইবার আমরা এইটি প্রোগ্রামিং ল্যাংগুয়েজে ইমপ্লিমেন্ট করতে পারি কিনা দেখি।

পাইথনঃ

Declaring a python function with an array

  
    def sort_bubblesort(my_list):
    # Here's our formula 😀
    for pos_upper in xrange(len(my_list)-1,0,-1):
        for i in xrange(pos_upper):
            if my_list[i] > my_list[i+1]:
               my_list[i], my_list[i+1] = my_list[i+1], my_list[i]
               print "pos_upper: " + str(pos_upper) + " i: " + str(i) + " my_list: " + str(my_list)
               return my_list

    if __name__ == "__main__":

    my_list = [4,26,93,17,77,3111111,44,55,20]
    print my_list
    print sort_bubblesort(my_list)

টাইম কমপ্লেক্সিটিঃ

উপরের j= 0 এর জন্য i, (n-1) বার ঘুরবে

j=1 এর জন্য i, (n-1) বার ঘুরবে ———————- ———————- j= (n-1) এর জন্য i , (n-1) বার ঘুরবে

তাহলে মোট ঘুরবে (n-1)*(n-1) n^2-n-n+1 n^2-2n+1

বিগ ও হিসেবে টাইম কমপ্লেক্সিটি হবে N^2 O(N^2)

Best কেস পারফরম্যান্স হলঃ O(N) Worst কেস পারফরম্যান্স হলঃ O(N^2)

Real Life Implementation:

কষ্টকর হলেও সত্য যে ইয়েল ওয়ার্ল্ডে বলতে গেলে এইটার তেমন কোন ইমপ্লিমেন্টশন নাই :p । আপনি তার কাজের ধরণ দেখেই বুঝতে পারছেন এইটা যেভাবে কাজ করে এইভাবে একচুয়েলি অনেক ডাটা নিয়ে কাজ করা অসম্ভব একটা ব্যাপার। আপনি যে সব প্রবলেমে দেখবেন ডাটা গুলো অলমোস্ট সর্টিং অবস্থায় আছে তখনি এলগোটি ব্যবহার করবেন।