সন্নিবেশ বাছাই

সন্নিবেশ বাছাই

Animation of insertion sort
শ্রেণী	Sorting algorithm
উপাত্ত সংগঠন	Array
প্রতিকূল অবস্থায় সময়	${\displaystyle O(n^{2})}$ comparisons and swaps
অনুকূল অবস্থায় সময়	${\displaystyle O(n)}$ comparisons, ${\displaystyle O(1)}$ swaps
সাধারণ অবস্থায় সময়	${\displaystyle O(n^{2})}$ comparisons and swaps
প্রতিকূল অবস্থায় গৃহীত মেমরি	${\displaystyle O(n)}$ total, ${\displaystyle O(1)}$ auxiliary

সন্নিবেশ বাছাই একটি সহজ বাছাই অ্যালগরিদম যা চূড়ান্ত সাজানো অ্যারে (বা তালিকা) একবারে একটি আইটেম তৈরি করে।Quicksort, heapsort, বা merge sort-এর মতো আরও উন্নত অ্যালগরিদমের তুলনায় বড় তালিকায় এটি অনেক কম কার্যকর।যাইহোক, সন্নিবেশ বাছাই বিভিন্ন সুবিধা প্রদান করে:

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

মানুষ যখন ব্রিজের হাতে কার্ড ম্যানুয়ালি বাছাই করে, তখন বেশিরভাগই এমন একটি পদ্ধতি ব্যবহার করে যা সন্নিবেশ সাজানোর মতো।

তথ্যসূত্র

1. Bentley, Jon (২০০০)। "Column 11: Sorting"। Programming Pearls (2nd সংস্করণ)। ACM Press / Addison-Wesley। পৃষ্ঠা 115–116। আইএসবিএন 978-0-201-65788-3। ওসিএলসি 1047840657।