ইনসারশন সর্ট বিশ্লেষণ

সিলেকশন সর্টের মত ইনসারশন সর্টও অ্যারের সূচকের উপর লুপ চালায়। এটা শুধু উপাদানলোরসূচক $1,2,3,\dots ,n-1$‍ এগুলোতে insert চালাবে। indexOfMinimum প্রতিবার চালাতে কিছুটা সময় নেয় যেটা নির্ভর করে সাজানো সাব-অ্যারের সাইজের উপর, insert এর ক্ষেত্রেও একই ঘটবে। আসলে, আমরা "ঘটবে" না বলে বলতে পারি "পারবে" এবং কেন আমরা সেটাই দেখব।

ধরে নেই আমরা এখন insert কল করব এবং যেই মানটি সাব-অ্যারে তে ঢুকবে সেটি সাব-অ্যারের প্রত্যেকটি ঘরের মানের চেয়ে ছোট হবে। উদাহরণস্বরূপ, যদি আমরা [2, 3, 5, 7, 11], এই সাব-অ্যারে তে 0 রাখতে চাই, তাহলে প্রত্যেকটি ঘরের মানকে এক ঘর ডানে সরে যেতে হবে। তাহলে, সাধারনভাবে, যদি আমরা $k$‍ সদস্য বিশিষ্ট একটি সাব-অ্যারেতে একটি মান ঢুকাতে চাই, সব $k$‍ কে হয়ত এক ঘর করে সরে যেতে হবে। একটি মান ঢুকাতে বাকি মানগুলোকে কত বার সরে যেতে হবে তা বের করতে কত লাইন কোড করতে হবে তা না গুণে বরং, আমরা ধরে নেই তা হবে একটি ধ্রুব সংখ্যা; ধ্রুবকটিকে বলতে পারি $c$‍। তথাপি, $c\cdot k$‍ পর্যন্ত লাইন প্রয়োজন হতে পারে $k$‍ সদস্যের একটি সাব-অ্যারেতে মান ঢুকাতে হলে।

মনে কর প্রত্যেকবার insert, কল করার পর, সাব-অ্যারে তে যে মানটি প্রবেশ করানো হচ্ছে তা তার বামপাশের অন্য সব মানের চেয়ে ছোট। যখন আমরা প্রথমবার insert কল করি, $k=1$‍। পরেরবার, $k=2$‍। তার পরেরবার, $k=3$‍। এবং এভাবেই, শেষ পর্যন্ত চলতে থাকবে যতক্ষণ পর্যন্ত $k=n-1$‍ না হচ্ছে। তাহলে, সর্টেড সাব-অ্যারে মানগুলো প্রবেশ করাতে মোট সময় প্রয়োজন

$c\cdot 1+c\cdot 2+c\cdot 3+\cdots c\cdot (n-1)=c\cdot (1+2+3+\cdots +(n-1))$‍ .

এটা হল একটি গাণিতিক ধারা, যদিও এটা $n-1$‍ গিয়ে শেষ হয় $n$‍ এ নয়। গাণিতিক ধারার সুত্র ব্যবহার করে, আমরা পাই যে সাজানো সাব-অ্যারেতে মানগুলো প্রবেশ করাতে মোট সময় প্রয়োজন

$c\cdot (n-1+1)((n-1)/2)=c{n}^2/2-cn/2$‍ .

big-Θ চিহ্ন ব্যবহার করে, আমরা এই ক্ষুদ্র মান $cn/2$‍ এবং ধ্রুব পদ $c$‍ ও 1/2 বাদ দিতে পারি এবং এই ক্ষেত্রে আমরা পাই মোট প্রয়োজনীয় সময় হল $\mathrm{\Theta }(n^2)$‍।

ইনসারশন সর্ট কি $\mathrm{\Theta }(n^2)$‍ এর চেয়ে কম সময়ে করা সম্ভব? হ্যাঁ সম্ভব। ধরি আমাদের একটি অ্যারে আছে [2, 3, 5, 7, 11], যেখানে সর্টেড সাব-অ্যারেতে প্রথম চারটি উপাদান আছে এবং আমরা 11 ঢুকাব। আমরা প্রথমেই, এখানে দেখতে পাব 11, 7 এর চেয়ে বড় এবং তাই সাব-অ্যারেতে কোন মানই ডান পাশে সরতে হবে না। তাহলে এই insert চালাতে একটি নির্দিষ্ট সময় লাগবে। ধরি এই প্রত্যেকবার insert চালানোর জন্য সময়ের পরিমাণ ধ্রুবক। কারণ এখানে $n-1$‍ বার insert কল হয়েছে, যদি প্রত্যেকটি কলের জন্য সময় একটি ধ্রুবক $c$‍ হয়, তাহলে মোট প্রয়োজনীয় সময় হবে $c\cdot (n-1)$‍, যেটা $\mathrm{\Theta }(n^2)$‍ হবে না, হবে $\mathrm{\Theta }(n)$‍।

এই ঘটনাগুলো কি কখনো ঘটতে পারে? প্রত্যেকবার insert কল করলে সাব-অ্যারের প্রত্যেকটি মানকে কি এক ঘর ডানে সরে যেতে হবে? প্রত্যেকবার insert কল করলে কি কোন মানকেই সরতে হবে না? উভয় প্রশ্নের উত্তরেই আমরা হ্যাঁ বলতে পারি। একটি insert কলে প্রত্যেকটি মানকেই সরে যেতে হবে যদি যে মানটি ঢুকানো হচ্ছে তা তার বামের সবগুলো মানের চেয়ে ছোট হয়। তাহলে, প্রত্যেকটি মানই যদি তার বামদিকের মানের চেয়ে ছোট হয়, ইনসারশন সর্টের জন্য মোট সময় লাগবে $\mathrm{\Theta }(n^2)$‍। প্রত্যেকটি মান তার বামদিকের মানগুলোর চেয়ে ছোট হবে এটা বলতে আসলে কি বুঝায়? অ্যারে টিকে বিপরীত ক্রমে সাজানো থাকতে হবে, যেমন [11, 7, 5, 3, 2]। তাহলে ইনসারশন সর্টের ক্ষেত্রে বিপরীত-ক্রমে সাজানো অ্যারে সবচেয়ে বাজে।

এর বিপরীত ক্ষেত্রে কি হতে পারে? যখন insert কল করা হয় তখন যদি যে মানটি ঢুকানো হচ্ছে তা তার বামের সবগুলো মানের চেয়ে বড় বা সমান হয় তাহলে কোন মানকেই সরে যেতে হবে না। তাহলে, প্রত্যেকটি মানই যদি তার বামদিকের মানের চেয়ে বড় বা সমান হয়, ইনসারশন সর্টের জন্য মোট সময় লাগবে $\mathrm{\Theta }(n)$‍। এরকম শুধু তখনই ঘটবে যখন অ্যারেটি আগে থেকেই সাজানো থাকবে এবং তাহলে ইনসারশন সর্টের ক্ষেত্রে আগে থেকে সাজানো অ্যারে সবচেয়ে ভালো।

ইনসারশন সর্টের জন্য প্রয়োজনীয় সময় নিয়ে আমরা আর কি বলতে পারি? মনে কর অ্যারেটি এলোমেলোভাবে আছে। তাহলে, আমরা আশা করতে পারি প্রত্যেকটি মান তার বামদিকের প্রায় অর্ধেক মানের চেয়ে ছোট হবে। এক্ষেত্রে, গড়ে $k$‍ উপাদানের একটি সাবঅ্যারেতে একটি insert কলের জন্য $k/2$‍ উপাদানকে সরে যেতে হবে। এতে সময় লাগবে সবচেয়ে বাজে ক্ষেত্রের সময়ের অর্ধেক। কিন্তু এ্যাসিম্প্টোটিক নোটেশান এর ক্ষেত্রে, যেখানে ধ্রুব সহগের কোন মূল্য নেই, সে ক্ষেত্রেও $\mathrm{\Theta }(n^2)$‍ সময়ই লাগবে, যেমনটা লাগবে সবচেয়ে বাজে ক্ষেত্রে।

কি হত যদি তুমি জানতে যে অ্যারেটি "প্রায় সাজানো" আছে: প্রত্যেকটি উপাদানের ক্ষেত্রে কোন একটি অবস্থান, যেমন ধর 17 থেকে শুরু হয় যেখান থেকে এটা সাজানো হবে? তখন প্রত্যেকটি insert কলের জন্য সর্বোচ্চ 17 টি উপাদান সরে যেতে হবে এবং $k$‍ উপাদানের একটি সাবঅ্যারেতে প্রত্যেকটি insert কলের জন্য সময় লাগবে $17\cdot c$‍। সামগ্রিকভাবে $n-1$‍ সংখ্যক insert কলের জন্য সময় লাগবে $17\cdot c\cdot (n-1)$‍, যেটা হল $\mathrm{\Theta }(n)$‍, যেমনটা হয় সবচেয়ে ভালো ক্ষেত্রে। তাহলে ইনসারশন সর্ট দ্রুত হয় যখন একটি প্রায় সাজানো অ্যারে দেওয়া হয়।

ইনসারশন সর্ট চালানোর সময়গুলো একসাথে নিলে:

যদি তুমি এটাকে সাধারনভাবে প্রকাশ করতে চাও যেটা সব ইনসারশন সর্টের ক্ষেত্রে প্রযোজ্য, তোমাকে বলতে হবে এর জন্য সময় লাগবে $O(n^2)$‍। তুমি বলতে পারনা যে সব ক্ষেত্রে সময় লাগবে $\mathrm{\Theta }(n^2)$‍, যেহেতু সবচেয়ে ভালো ক্ষেত্রে সময় লাগে $\mathrm{\Theta }(n)$‍। আর তুমি এটাও বলতে পারনা যে সব ক্ষেত্রে সময় লাগবে $\mathrm{\Theta }(n)$‍, যেহেতু সবচেয়ে বাজে ক্ষেত্রে সময় লাগে $\mathrm{\Theta }(n^2)$‍।

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।