বাবল সর্ট অ্যালগরিদম

সর্টিং কী?

সর্টিং হল স্ট্রাকচারের উপাদানগুলো যৌক্তিকভাবে সাজানো। অর্থাৎ উপাদানগুলো ছোট থেকে বড় এর দিকে সাজানো (Ascending Order), বড় থেকে ছোট এর দিকে সাজানো (Descending Order)। যেমন আমাদের কাছে কিছু এলোমেলো সংখ্যা রয়েছে। আমরা চাচ্ছি যেগুলোকে ছোট থেকে বড় আকারে সাজাতে। এ সাজানো বড় থেকে ছোট হতে পারে বা ছোট থেকে বড় হতে পারে। ইংরেজিতে যাকে বলে Sorting। এই সাজানোর আইডিয়াটা অনেক সহজ মনে হলেও বাস্তব জীবনে এর অনেক ব্যবহার রয়েছে।

 

বাবল সর্ট : 

বাবল অর্থ হচ্ছে বুদ বুদ। এটি কে বাবল সর্ট নামকরণ করার কারণ হচ্ছে bubbles rising surface এর মত উপাদানগুলি সঠিক ক্রমে চলে আসে। সে যাই হোক bubbles rising surface কিভাবে সঠিক ক্রমে চলে আসে সেটিতো আর আমরা দেখতে যায়নি। আমরা নিচের অ্যারের মাধ্যমে সেটি কিভাবে কাজ করে দেখি।

array1581631821109

 

 

এখানে প্রথমে 8 এর সাথে 15 এর তুলনা করবে। যাচাই করে দেখবে 8; 15 এর চাইতে ছোট কিনা। যেহেতু 8; 15 এর চাইতে ছোট, তাই 8 এর স্থানে 15 চলে যাবে এবং 15 এর স্থানে 8 চলে আসবে।

array8151631821109

 

 

16 এর সাথে 15 এর তুলনা করবে। যাচাই করে দেখবে 16; 15 এর চাইতে ছোট কিনা। যেহেতু না, তাই কোন আদল বদল হবে না।

array8151631821109

 

 

3 এর সাথে 16 এর তুলনা করবে। যাচাই করে দেখবে 3; 16 এর চাইতে ছোট কিনা। যেহেতু 3; 16 এর চাইতে ছোট, তাই 3 এর স্থানে 16 চলে যাবে এবং 16 এর স্থানে 3 চলে আসবে।

array8153161821109

 

 

18 এর সাথে 16 এর তুলনা করবে। যাচাই করে দেখবে 18; 16 এর চাইতে ছোট কিনা। যেহেতু না, তাই কোন আদল বদল হবে না।

array8153161821109

 

 

21 এর সাথে 18 এর তুলনা করবে। যাচাই করে দেখবে 21; 18 এর চাইতে ছোট কিনা। যেহেতু না, তাই কোন আদল বদল হবে না।

array8153161821109

 

 

10 এর সাথে 21 এর তুলনা করবে। যাচাই করে দেখবে 10; 21 এর চাইতে ছোট কিনা। যেহেতু 10; 21 এর চাইতে ছোট, তাই 10 এর স্থানে 21 চলে যাবে এবং 21 এর স্থানে 10 চলে আসবে।

array8153161810219

 

 

9 এর সাথে 21 এর তুলনা করবে। যাচাই করে দেখবে 9; 21 এর চাইতে ছোট কিনা। যেহেতু 9; 21 এর চাইতে ছোট, তাই 9 এর স্থানে 21 চলে যাবে এবং 21 এর স্থানে 9 চলে আসবে।

array8153161810921

 

 

এখানে আমরা লক্ষ করলে দেখবে সবছেয়ে ডানের সংখ্যাটি 21 যা সবার চাইতে বড়। যেহেতু সবছেয়ে বড় সংখ্যা 21 সবার শেষে চলে  এসেছে তাই আর আমাদের 21 পর্যন্ত যাওয়ার প্রয়োজন নাই। এবার আমরা শুরু থেকে 9 পর্যন্ত তুলনা করা শুরু করব।

array8153161810921

 

 

15 এর সাথে 8 এর তুলনা করবে। যাচাই করে দেখবে 15; 8 এর চাইতে ছোট কিনা। যেহেতু না, তাই কোন আদল বদল হবে না।

array8153161810921

 

 

3 এর সাথে 15 এর তুলনা করবে। যাচাই করে দেখবে 3; 15 এর চাইতে ছোট কিনা। যেহেতু 3; 15 এর চাইতে ছোট, তাই 15 এর স্থানে 3 চলে যাবে এবং 3 এর স্থানে 15 চলে আসবে।

array8315161810921

 

 

16 এর সাথে 15 এর তুলনা করবে। যাচাই করে দেখবে 16; 15 এর চাইতে ছোট কিনা। যেহেতু না, তাই কোন আদল বদল হবে না।

array8315161810921

 

 

18 এর সাথে 16 এর তুলনা করবে। যাচাই করে দেখবে 18; 16 এর চাইতে ছোট কিনা। যেহেতু না, তাই কোন আদল বদল হবে না।

array8315161810921

 

 

10 এর সাথে 18 এর তুলনা করবে। যাচাই করে দেখবে 10; 18 এর চাইতে ছোট কিনা। যেহেতু 10; 18 এর চাইতে ছোট, তাই 10 এর স্থানে 18 চলে যাবে এবং 18 এর স্থানে 10 চলে আসবে।

array8315161018921

 

 

9 এর সাথে 18 এর তুলনা করবে। যাচাই করে দেখবে 9; 18 এর চাইতে ছোট কিনা। যেহেতু 9; 18 এর চাইতে ছোট, তাই 9 এর স্থানে 18 চলে যাবে এবং 18 এর স্থানে 9 চলে আসবে।

array8315161091821

 

 

আমরা যেহেতু আগেই বলেছিলাম আমরা 9 পর্যন্ত তুলনা করব। এখানে আমরা লক্ষ করলে দেখব সবছেয়ে ডানের সংখ্যাটি 18 যা সবার চাইতে বড়। যেহেতু এখানে সবছেয়ে বড় সংখ্যা 18 সবার শেষে চলে  এসেছে তাই আর আমাদের 18 পর্যন্ত যাওয়ার প্রয়োজন নাই। এবার আমরা শুরু থেকে আবার 9 পর্যন্ত তুলনা করা শুরু করব।

array8315161091821

 

 

3 এর সাথে 8 এর তুলনা করবে। যাচাই করে দেখবে 3; 8 এর চাইতে ছোট কিনা। যেহেতু 3; 8 এর চাইতে ছোট, তাই 3 এর স্থানে 8 চলে যাবে এবং 8 এর স্থানে 3 চলে আসবে।

array3815161091821

 

 

15 এর সাথে 8 এর তুলনা করবে। যাচাই করে দেখবে 15; 8 এর চাইতে ছোট কিনা। যেহেতু না, তাই কোন আদল বদল হবে না।

array3815161091821

 

 

16 এর সাথে 15 এর তুলনা করবে। যাচাই করে দেখবে 16; 15 এর চাইতে ছোট কিনা। যেহেতু না, তাই কোন আদল বদল হবে না।

array3815161091821

 

 

10 এর সাথে 16 এর তুলনা করবে। যাচাই করে দেখবে 10; 16 এর চাইতে ছোট কিনা। যেহেতু 10; 16 এর চাইতে ছোট, তাই 10 এর স্থানে 16 চলে যাবে এবং 16 এর স্থানে 10 চলে আসবে।

array3815101691821

 

 

9 এর সাথে 16 এর তুলনা করবে। যাচাই করে দেখবে 9; 16 এর চাইতে ছোট কিনা। যেহেতু 9; 16 এর চাইতে ছোট, তাই 9 এর স্থানে 16 চলে যাবে এবং 16 এর স্থানে 9 চলে আসবে।

array3815109161821

 

 

আমরা যেহেতু আগেই বলেছি আমরা 9 পর্যন্ত তুলনা করব। এখানে আমরা লক্ষ করলে দেখব সবছেয়ে ডানের সংখ্যাটি 16 যা সব চাইতে বড়। যেহেতু এখানে সবছেয়ে বড় সংখ্যা 16 সবার শেষে চলে  এসেছে তাই আর আমাদের 16 পর্যন্ত যাওয়ার প্রয়োজন নাই। এবার আমরা শুরু থেকে আবার 9 পর্যন্ত তুলনা করা শুরু করব।

array3815109161821

 

 

8 এর সাথে 3 এর তুলনা করবে। যাচাই করে দেখবে 8; 3 এর চাইতে ছোট কিনা। যেহেতু না, তাই কোন আদল বদল হবে না।

array3815109161821

 

 

15 এর সাথে 8 এর তুলনা করবে। যাচাই করে দেখবে 15; 8 এর চাইতে ছোট কিনা। যেহেতু না, তাই কোন আদল বদল হবে না।

array3815109161821

 

 

10 এর সাথে 15 এর তুলনা করবে। যাচাই করে দেখবে 10; 15 এর চাইতে ছোট কিনা। যেহেতু 10; 15 এর চাইতে ছোট, তাই 10 এর স্থানে 15 চলে যাবে এবং 15 এর স্থানে 10 চলে আসবে।

array3810159161821

 

 

9 এর সাথে 15 এর তুলনা করবে। যাচাই করে দেখবে 9; 15 এর চাইতে ছোট কিনা। যেহেতু 9; 15 এর চাইতে ছোট, তাই 9 এর স্থানে 15 চলে যাবে এবং 15 এর স্থানে 9 চলে আসবে।

array3810915161821

 

 

আমরা যেহেতু আগেই বলেছি আমরা 9 পর্যন্ত তুলনা করব। এখানে আমরা লক্ষ করলে দেখব সবছেয়ে ডানের সংখ্যাটি 15 যা সব চাইতে বড়। যেহেতু এখানে সবছেয়ে বড় সংখ্যা 15 সবার শেষে চলে  এসেছে তাই আর আমাদের 15 পর্যন্ত যাওয়ার প্রয়োজন নাই। এবার আমরা শুরু থেকে আবার 9 পর্যন্ত তুলনা করা শুরু করব।

array3810915161821

 

 

8 এর সাথে 3 এর তুলনা করবে। যাচাই করে দেখবে 8; 3 এর চাইতে ছোট কিনা। যেহেতু না, তাই কোন আদল বদল হবে না।

array3810915161821

 

 

10 এর সাথে 8 এর তুলনা করবে। যাচাই করে দেখবে 10; 8 এর চাইতে ছোট কিনা। যেহেতু না, তাই কোন আদল বদল হবে না।

array3810915161821

 

 

9 এর সাথে 10 এর তুলনা করবে। যাচাই করে দেখবে 9; 10 এর চাইতে ছোট কিনা। যেহেতু 9; 10 এর চাইতে ছোট, তাই 9 এর স্থানে 10 চলে যাবে এবং 10 এর স্থানে 9 চলে আসবে।

array3891015161821

 

 

আমরা যেহেতু আগেই বলেছি আমরা 9 পর্যন্ত তুলনা করব। এখানে আমরা লক্ষ করলে দেখব সবছেয়ে ডানের সংখ্যাটি 10 যা সব চাইতে বড়। যেহেতু এখানে সবছেয়ে বড় সংখ্যা 10 সবার শেষে চলে  এসেছে তাই আর আমাদের 10 পর্যন্ত যাওয়ার প্রয়োজন নাই। এবার আমরা শুরু থেকে আবার 9 পর্যন্ত তুলনা করা শুরু করব।

array3891015161821

 

 

8 এর সাথে 3 এর তুলনা করবে। যাচাই করে দেখবে 8; 3 এর চাইতে ছোট কিনা। যেহেতু না, তাই কোন আদল বদল হবে না।

array3891015161821

 

 

9 এর সাথে 8 এর তুলনা করবে। যাচাই করে দেখবে 9; 8 এর চাইতে ছোট কিনা। যেহেতু না তাই কোন আদল বদল হবে না।

array3891015161821

 

 

আমরা যেহেতু আগেই বলেছি আমরা 9 পর্যন্ত তুলনা করব। এখানে আমরা লক্ষ করলে দেখব সবছেয়ে ডানের সংখ্যাটি 9 যা সব চাইতে বড়। যেহেতু এখানে সবছেয়ে বড় সংখ্যা 9 সবার শেষে চলে এসেছে তাই আর আমাদের 9 পর্যন্ত যাওয়ার প্রয়োজন নাই। এবার আমরা শুরু থেকে আবার 8 পর্যন্ত তুলনা করা শুরু করব।

array3891015161821

 

 

8 এর সাথে 3 এর তুলনা করবে। যাচাই করে দেখবে 8; 3 এর চাইতে ছোট কিনা। যেহেতু না তাই কোন আদল বদল হবে না।

array3891015161821

 

 

এখন  অ্যারের সকল ইলিমেন্টের সাথে সাথে সকল ইলিমেন্টের তুললা করা হয়ে গেছে। আমরা লক্ষ করলে দেখব আমাদের অ্যারেটির সংখ্যাগুলো বড় থেকে ছোট আকারে সাজানো হয়ে গেছে।

array3891015161821

 

 

যেহেতু আমরা অ্যালগরিদমটি কিভাবে কাজ করে বুঝতে পেরেছি। তাই এবার আমরা প্রোগ্রামিং এর সাহায্যে বাবল সর্ট অ্যালগরিদমটি সমাধান করব। আমরা এখানে জাভা এবং সি দুটি ল্যাংগুয়েজের  এর সাহায্যে প্রোগ্রামটি সমাধান করে দেখিয়েছি।

 

জাভা  এর সাহায্যে:

 

 

সি  এর সাহায্যে:

 

প্রোগ্রামটি কিভাবে কাজ করে তা নিচের চিত্রের মাধ্যমে বর্ণনা করা হল:

 

Advantages of Bubble short: 

  • Easy to understand.
  • Easy to implement.
  • In-place, no external memory is needed.
  • Performs greatly when the array is almost sorted.

Disadvantages of Bubble short:

  •  Bubble sort has several disadvantages compared to other sorting algorithms.
  •  It is very slow and runs in O(n^2) time in worst as well as an average case.
  • There are many sorting algorithms that run in linear time i.e O(n) and some algorithms in O(nlogn).
  • The only advantage of bubble sort is that it is easy to understand
  • The loop continues to run even if the array is sorted if the code is not optimized.

 

ধন্যবাদ।

Level 0

আমি মোহাম্মদ আক্তারুজ্জামান। বিশ্বের সর্ববৃহৎ বিজ্ঞান ও প্রযুক্তির সৌশল নেটওয়ার্ক - টেকটিউনস এ আমি 1 বছর যাবৎ যুক্ত আছি। টেকটিউনস আমি এ পর্যন্ত 4 টি টিউন ও 0 টি টিউমেন্ট করেছি। টেকটিউনসে আমার 1 ফলোয়ার আছে এবং আমি টেকটিউনসে 1 টিউনারকে ফলো করি।

Hi, I am Aktaruzzaman. I am a Professional Graphic and Front End Web developer. I also work as a Java programmer. Thanks For Visiting My Profile.


টিউনস


আরও টিউনস


টিউনারের আরও টিউনস


টিউমেন্টস