সন্নিবেশ বাছাই
টেমপ্লেট:তথ্যছক অ্যালগরিদমসন্নিবেশ বাছাই একটি সহজ বাছাই অ্যালগরিদম যা চূড়ান্ত সাজানো অ্যারে (বা তালিকা) একবারে একটি আইটেম তৈরি করে।Quicksort, heapsort, বা merge sort-এর মতো আরও উন্নত অ্যালগরিদমের তুলনায় বড় তালিকায় এটি অনেক কম কার্যকর।যাইহোক, সন্নিবেশ বাছাই বিভিন্ন সুবিধা প্রদান করে:
- সহজ বাস্তবায়ন: জন বেন্টলি একটি তিন-লাইন C++ সংস্করণ এবং একটি পাঁচ-লাইন অপ্টিমাইজড সংস্করণ দেখায়[১]
- (বেশ) ছোট ডেটা সেটের জন্য দক্ষ, অনেকটা অন্যান্য দ্বিঘাত বাছাই অ্যালগরিদমের মতো
- অন্যান্য সাধারণ চতুর্ঘাতিক (অর্থাৎ, O ( n 2 )) অ্যালগরিদম যেমন নির্বাচন বাছাই বা বুদবুদ সাজানোর তুলনায় অনুশীলনে বেশি দক্ষ
- অভিযোজিত, অর্থাৎ, ইতিমধ্যেই যথেষ্ট পরিমাণে সাজানো ডেটা সেটগুলির জন্য দক্ষ: সময় জটিলতা হল O ( kn ) যখন ইনপুটের প্রতিটি উপাদান তার সাজানো অবস্থান থেকে টেমপ্লেট:Mvar স্থানের বেশি দূরে থাকে না
- স্থিতিশীল ; অর্থাৎ, সমান কী সহ উপাদানগুলির আপেক্ষিক ক্রম পরিবর্তন করে না
- জায়গায় ; অর্থাৎ, শুধুমাত্র অতিরিক্ত মেমরি স্থানের একটি ধ্রুবক পরিমাণ O(1) প্রয়োজন
- অনলাইন ; অর্থাত্, এটি প্রাপ্ত হিসাবে একটি তালিকা বাছাই করতে পারেন
মানুষ যখন ব্রিজের হাতে কার্ড ম্যানুয়ালি বাছাই করে, তখন বেশিরভাগই এমন একটি পদ্ধতি ব্যবহার করে যা সন্নিবেশ সাজানোর মতো।