জাভাস্ক্রিপ্টে ইন্সারশন সোর্ট ইমপ্লিমেন্টেশন

ইন্সারশন সোর্ট

এটি একটি সিম্পল কমপ্যারিজন সোর্ট যা অ্যারে সর্ট করতে ব্যবহৃত হয়। কমপ্যারিজন সোর্ট সর্ট করার চেষ্টা কর रहे বর্তমান ভ্যালুটিকে অ্যারে-এর অন্যান্য ভ্যালুতুলনার সাথে তুলনা করে। এটি একবারে একটি আইটেম নিয়ে কাজ করে এবং প্রতিটি আইটেমকে সঠিক প্লেসমেন্টে রাখে যাতে সর্টেড অ্যারে পাওয়া যায়।

দরআসল, ইন্সারশন সোর্ট কিছু এডভান্সড অ্যালগরিদম (যেমন হিপ সোর্ট বা মার্জ সোর্ট) কতটা ইফিশিয়েন্ট নয়। বড় প্রোগ্রামের ক্ষেত্রে এটি ভালো অপশন নয়। কিন্তু এর লো হিডেন কনস্ট্যান্ট ভ্যালু-এর কারণে ছোট অ্যারে-র জন্য এটি হিপ বা কুইক সোর্টের চেয়ে কখনো কখনো আউটপারফর্ম করে।

ইন্সারশন সোর্ট বাম থেকে ডান দিকে অ্যারে ওভার মুভ করে। এটি কারেন্ট আইটেম-কে 'কী' হিসেবে ব্যবহার করে এবং সেই কী-এর বাম পাশের ভ্যালুগুলোর মধ্যে সার্চ করে কী-এর সঠিক লোকেশন খুঁজে বের করে।

অ্যালগরিদম

উদাহরণস্বরূপ অ্যারে: 0, -3, 5, 8, 2, 7, 6

• Iteration 0: শুধু আনসর্টেড অ্যারে: 0, -3, 5, 8, 2, 7, 6
• Iteration 1: কী = -3 (ইন্ডেক্স ১)। -3, 0-এর চেয়ে ছোট, তাই 0-এর বামে চলে গিয়েছে: -3, 0, 5, 8, 2, 7, 6
• Iteration 2: কী = 5 (ইন্ডেক্স ২)। বামের ভ্যালু -3, 0 - সাথে তুলনা করে সঠিক প্লেসমেন্টে: -3, 0, 5, 8, 2, 7, 6
• Iteration 3: কী = 8। বামের এলিমেন্টগুলো সাথে তুলনা: -3, 0, 5, 8, 2, 7, 6
• Iteration 4: কী = 2। বামের ভ্যালুগুলোর সাথে তুলনা করে সর্টেড পজিশনে: -3, 0, 2, 5, 8, 7, 6

শেষ ইটারেশনের পর সর্টেড অ্যারে: -3, 0, 2, 5, 6, 7, 8

উদাহরণ

<html> <head> 
<script> 
  function iSort(array) {
    for (var p = 1; p < array.length; p++) {
      if (array[p] < array[0]) {
        array.unshift(array.splice(p, 1)[0]);
      } else if (array[p] > array[p-1]) {
        continue;
      } else {
        for (var q = 1; q < p; q++) {
          if (array[p] > array[q-1] && array[p] < array[q]) {
            array.splice(q, 0, array.splice(p, 1)[0]);
          }
        }
      }
    }
    return array;
  }
  document.write(iSort([0, -3, 5, 8, 2, 7, 6]));
</script> 
</body> </html>

আউটপুট

-3,0,2,5,6,7,8

ব্যাখ্যা

ইন্সারশন সোর্টের টাইম কমপ্লেক্সিটি: বেস্ট কেস O(n), অ্যারেজ/ওয়ার্স্ট কেস O(n²)। স্পেস কমপ্লেক্সিটি O(1)। এটি স্ট্যাবল সোর্টিং অ্যালগরিদম।