সর্টিং কী?

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

বাবল সর্ট : 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

ধন্যবাদ।