বাবল বাছাই বনাম নির্বাচন সাজানোর
বাবল সর্ট হল একটি সাজানোর অ্যালগরিদম যা পাশে থাকা উপাদানগুলির জোড়ার তুলনা করার সময় বারবার সাজানোর তালিকার মধ্য দিয়ে কাজ করে। যদি উপাদানগুলির একটি জোড়া ভুল ক্রমে থাকে তবে সেগুলিকে সঠিক ক্রমে স্থাপন করতে অদলবদল করা হয়। এই ট্রাভার্সালটি পুনরাবৃত্তি করা হয় যতক্ষণ না আর কোন অদলবদলের প্রয়োজন হয়। নির্বাচন বাছাই হল একটি সাজানোর অ্যালগরিদম, যা তালিকার সর্বনিম্ন উপাদান খুঁজে বের করে এবং প্রথম উপাদানটির সাথে অদলবদল করে শুরু হয়। অদলবদল করা উপাদানগুলিকে ক্রমানুসারে রেখে এই প্রক্রিয়াটি তালিকার বাকি অংশের জন্য পুনরাবৃত্তি করা হয়।
বাবল সাজানো কি?
বাবল সর্ট হল একটি সাজানোর অ্যালগরিদম যা পাশে থাকা উপাদানগুলির জোড়ার তুলনা করার সময় বারবার সাজানোর তালিকার মধ্য দিয়ে কাজ করে। যদি উপাদানগুলির একটি জোড়া ভুল ক্রমে থাকে তবে সেগুলিকে সঠিক ক্রমে স্থাপন করতে অদলবদল করা হয়। এই ট্রাভার্সালটি পুনরাবৃত্তি করা হয় যতক্ষণ না আর কোন অদলবদলের প্রয়োজন হয় (যার মানে তালিকাটি সাজানো হয়)। যেহেতু একটি বুদবুদ পৃষ্ঠে আসার সাথে সাথে তালিকার ছোট উপাদানগুলি শীর্ষে আসে, তাই এটিকে বুদবুদ সাজানোর নাম দেওয়া হয়। বুদ্বুদ সাজানোর একটি খুব সাধারণ বাছাই অ্যালগরিদম কিন্তু n উপাদানগুলির সাথে একটি তালিকা বাছাই করার সময় এটিতে O(n2) এর গড় কেস টাইম জটিলতা রয়েছে। এই কারণে, বুদ্বুদ সাজানোর উপাদান একটি বড় সংখ্যা সঙ্গে তালিকা বাছাই জন্য উপযুক্ত নয়. কিন্তু এর সরলতার কারণে, অ্যালগরিদমের ভূমিকার সময় বুদ্বুদ সাজানো শেখানো হয়।
নির্বাচন সাজানো কি?
নির্বাচন বাছাই হল আরেকটি সাজানোর অ্যালগরিদম যা তালিকায় ন্যূনতম উপাদান খুঁজে বের করে প্রথম উপাদানের সাথে অদলবদল করে শুরু হয়।তারপরে ন্যূনতম উপাদানটি তালিকার অবশিষ্টাংশ থেকে পাওয়া যায় (দ্বিতীয় উপাদান থেকে তালিকার শেষ উপাদান পর্যন্ত) এবং দ্বিতীয় উপাদানটির সাথে অদলবদল করা হয়। অদলবদল করা উপাদানগুলিকে ক্রমানুসারে রেখে এই প্রক্রিয়াটি তালিকার বাকি অংশের জন্য পুনরাবৃত্তি করা হয়। তাই নির্বাচন সাজানোর ক্ষেত্রে, অ্যালগরিদমের যেকোনো ধাপে, তালিকাটিকে দুটি ভাগে ভাগ করা হয় যেখানে একটি অংশে সাজানো উপাদান থাকে এবং অন্য অংশে সাজানো উপাদান থাকে না। অ্যালগরিদম এগিয়ে যাওয়ার সাথে সাথে সাজানো তালিকা বাম থেকে ডানে বাড়তে থাকে। নির্বাচনের সাজানোর ক্ষেত্রে O(n2) এর গড় কেস টাইম জটিলতাও রয়েছে। তাই এটি বড় তালিকা বাছাই করার জন্যও উপযুক্ত নয়৷
বাবল সাজানো এবং নির্বাচন সাজানোর মধ্যে পার্থক্য কী?
যদিও বুদ্বুদ সাজানো এবং নির্বাচন সাজানোর অ্যালগরিদম উভয়ের ক্ষেত্রেই O(n2) এর গড় কেস টাইম জটিলতা রয়েছে, তবে বাবল সাজানোর ক্ষেত্রে প্রায় সব সময়ই সিলেকশন সাজানোর কাজ করা হয়। এটি দুটি অ্যালগরিদমের জন্য প্রয়োজনীয় অদলবদলের সংখ্যার কারণে (বাবল সাজানোর জন্য আরও অদলবদল প্রয়োজন)।কিন্তু বুদবুদ সাজানোর সরলতার কারণে এর কোডের আকার খুবই ছোট। স্থিতিশীলতা এই দুটি অ্যালগরিদমের আরেকটি পার্থক্য। একটি স্থিতিশীল বাছাই অ্যালগরিদম, একটি বাছাই অ্যালগরিদম যা রেকর্ডের ক্রম ধরে রাখে যদি তালিকায় একটি সমান মানের উপাদান থাকে। সেই অর্থে, নির্বাচনের সাজানো একটি স্থিতিশীল অ্যালগরিদম নয় যেখানে বুদবুদ সাজানোর একটি স্থিতিশীল অ্যালগরিদম৷
