বাবল সর্ট এলগরিদম

বাবল সর্টের মুল ব্যাপারটা হল প্রতিটি এলিমেন্টকে তার নিকটতম এলিমেন্টের সাথে তুলনা করতে হবে। যদি পূর্বেকার এলিমেন্ট বড় হয় তাহলে তাদের মধ্যে সোয়াপ করতে হবে, নাহলে কিছুই করতে হবেনা। আর এভাবে 1----- N পর্যন্ত চলতে থাকবে।

যেমন নিচের ৮ সংখ্যার ক্ষেত্রে যদি তা করিঃ 

৬,৫,৩,১,৮,৫,২,৪

------------

৫,৬,৩,১,৮,৫,২,৪

৫,৩,৬,১,৮,৫,২,৪

৫,৩,১,৬,৮,৫,২,৪

৫,৩,১,৬,৮,৫,২,৪

৫,৩,১,৬,৫,৮,২,৪

৫,৩,১,৬,৫,২,৮,৪

৫,৩,১,৬,৫,২,৪,৮ 

প্রথমে ০ এবং ১ নাম্বার ইনডেক্সকে তুলনা করেছি, তারপর ১,২ নাম্বার এভাবে ৭ এবং ৮ নাম্বার পর্যন্ত তুলনা করছি এবং অদল বদল করছি। পুরো এই কাজটা আমাকে করতে হচ্ছে ৭ বারে। এখানে আসলে নিন্মোক্ত ইন্ডেক্সগুলো আমি পর পর তুলনা করছি।

০,১

১,২

২,৩

৩,৪

৪,৫

৫,৬

৬,৭

৭,৮
বুঝতে সমস্যা হলে এই ছবিটি দেখা যেতে পারে- 

বাবল সর্ট সিমুলেশন

এখন এটি যদি প্রোগ্রামিং এর সাহায্যে করি তাহলে কিভাবে করতে হবে?

আমাকে শুন্য থেকে শুরু করে (N-1) পর্যন্ত লুপ চালাতে হবে। কারন (N-1)  ইনডেক্সে  গেলেই আমি N  কে পেয়ে যাচ্ছি। উপরের কাজটির জন্য লুপটি লিখে ফেলি তাহলেঃ

 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;  
 }  
 }   

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

মানে, উপরের ঐ কাজটাকে আমাকে আরো কয়েকবার করতে হবে। সর্বোচ্চ N-1  বার করলে আমার নাম্বারটা পুরোপুরি সর্ট হবে। তাহলে উপরের অ্যারেটির জন্য আমাকে কাজ করতে হচ্ছে, ৭ বার।

তাহলে আমাদের উপরের লুপকে আরো (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;  
 }  
 }  
 }  

দ্বিতীয় স্টেপে এরকম হবেঃ  

৩,৫,১,৬,৫,২,৪,৮

৩,১,৫,৬,৫,২,৪,৮

৩,১,৫,৬,৫,২,৪,৮

৩,১,৫,৫,৬,২,৪,৮

৩,১,৫,৫,২,৬,৪,৮

৩,১,৫,৫,২,৪,৬,৮

৩,১,৫,৫,২,৪,৬,৮

তৃতীয় স্টেপঃ  

১,৩,৫,৫,২,৪,৬,৮

১,৩,৫,৫,২,৪,৬,৮

১,৩,৫,৫,২,৪,৬,৮

১,৩,৫,২,৫,৪,৬,৮

১,৩,৫,২,৪,৫,৬,৮

১,৩,৫,২,৪,৫,৬,৮

১,৩,৫,২,৪,৫,৬,৮

-----------

-----------

N-1   স্টেপ  শেষেঃ   

১,২,৩,৪,৫,৬,৭,৮ 

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

উপরের 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)