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

উইকিপিডিয়া, মুক্ত বিশ্বকোষ থেকে
সন্নিবেশ বাছাই
Insertion sort.gif
Animation of insertion sort
শ্রেণীSorting algorithm
উপাত্ত সংগঠনArray
প্রতিকূল অবস্থায় সময় comparisons and swaps
অনুকূল অবস্থায় সময় comparisons, swaps
সাধারণ অবস্থায় সময় comparisons and swaps
প্রতিকূল অবস্থায় গৃহীত মেমরি total, auxiliary

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

  • সহজ বাস্তবায়ন: জন বেন্টলি একটি তিন-লাইন C++ সংস্করণ এবং একটি পাঁচ-লাইন অপ্টিমাইজড সংস্করণ দেখায় [১]
  • (বেশ) ছোট ডেটা সেটের জন্য দক্ষ, অনেকটা অন্যান্য দ্বিঘাত বাছাই অ্যালগরিদমের মতো
  • অন্যান্য সাধারণ চতুর্ঘাতিক (অর্থাৎ, O ( n 2 )) অ্যালগরিদম যেমন নির্বাচন বাছাই বা বুদবুদ সাজানোর তুলনায় অনুশীলনে বেশি দক্ষ
  • অভিযোজিত, অর্থাৎ, ইতিমধ্যেই যথেষ্ট পরিমাণে সাজানো ডেটা সেটগুলির জন্য দক্ষ: সময় জটিলতা হল 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 Bentley, Jon (2000). "Column 11: Sorting". Programming Pearls (2nd ed.). ACM Press / Addison-Wesley. pp. 115–116. ISBN 978-0-201-65788-3. OCLC 1047840657.