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