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

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

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

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

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

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