ইনসারশন সর্ট

বিভিন্ন পদ্ধতিতে সর্ট করা যায়। সিলেকশন সর্টে, অ্যারের প্রথম দিকের সাব-অ্যারে সর্ট করা হয়, কিন্তু শেষের দিকের সাব-অ্যারে সর্ট করা হয় না। সিলেকশন সর্ট অবিন্যস্ত সাব-অ্যারে থেকে উপাদান নিয়ে বিন্যস্ত সাব-অ্যারেতে প্রবেশ করায়।

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

এটিই হল ইনসারশন সর্টের মূল ভিত্তি। ইন্ডেক্স 1 থেকে শুরু করে অ্যারের মধ্যে লুপ করে সর্ট করা। প্রত্যেকটি নতুন স্থান হল একটি নতুন তাসের মত যা বিন্যস্ত সাব-অ্যারের সঠিক স্থানে নিযুক্ত করতে হবে। নিচে এটির কার্যক্রম দেখানো হল:

অ্যারের ক্ষেত্রে, ইন্ডেক্স 0 থেকে ইন্ডেক্স$5$5 পর্যন্ত অ্যারে সুবিন্যস্ত এবং আমরা ইন্ডেক্স 6 এ উপাদানটি রাখতে চাই, যেন ইন্ডেক্স 0 থেকে ইন্ডেক্স 6 পর্যন্ত সাব-অ্যারে সুবিন্যস্ত থাকে। আমরা এখানে এভাবে শুরু করিঃ

সুবিন্যস্ত হওয়ার পর সাব-অ্যারেকে এমন দেখাবেঃ

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

এখন, আমরা key কে 5 নং স্থানের উপাদানের সাথে তুলনা করবো। দেখা যায় যে, key (5) হল 5 নং স্থানের উপাদান (13) থেকে ছোট এবং এজন্য আমরা উপাদানকে 6 নং স্থানে নেইঃ

লক্ষ্য কর, slide শুধু উপানাদকে তার অবস্থান থেকে ডানদিকে নেয়। পরবর্তীতে, আমরা key কে 4 নং অবস্থানের উপাদানের সাথে তুলনা করি। দেখা যায় যে, key (5) হল 4 নং স্থানের উপাদান (10) থেকে ছোট এবং উপাদানকে সরাইঃ

তারপর, আমরা key কে 3 নং উপাদানের সাথে তুলনা করি এবং উপাদানকে সরাইঃ

একই কাজ 2 নং স্থানের উপাদানের সাথেও করিঃ

এখন আমরা 1 নং স্থানের উপাদানে এসেছি, যার মান হল 3। এই উপাদানটি key থেকে ছোট এবং আমরা এটি সরাই না। বরং, আমরা key কে এই উপাদানের ডানদিকে নেই (অর্থাৎ 2 নং স্থানে), যার উপাদান ডানদিকে নেওয়া হয়েছে। ফলাফলস্বরূপ সাব-অ্যারের ইন্ডেক্স 0 থেকে ইন্ডেক্স 6 পর্যন্ত সুবিন্যস্ত হয়েছেঃ

ইনসারশন সর্টে প্রতিনিয়ত দিয়ে দেওয়া উপাদান সাব-অ্যারের বামদিকে বিন্যস্ত করা হয়। শুরুতে, আমরা বলতে পারি যে, সাব-অ্যারের ইন্ডেক্স 0 সুবিন্যস্ত আছে, কারণ এটিতে শুধু একটি উপাদানই আছে এবং কীভাবে একটি উপাদান সুবিন্যস্ত না হতে পারে? এটি অবশ্যই সুবিন্যস্ত। একটি উদাহরণ দেখা যাক। নিচে আমাদের শুরুর অ্যারে দেওয়া হল:

যেহেতু সাব-অ্যারেতে এখন শুধু ইন্ডেক্স 0 আছে তাই এটি সুবিন্যস্ত, প্রথম key হল ইন্ডেক্স 1 এ রয়েছে। (সুবিন্যস্ত সাব-অ্যারেকে লাল, key কে হলুদ এবং বিন্যস্ত করতে হবে সেই অংশকে নীল রঙ দিয়ে প্রকাশ করা হয়।) আমরা key কে সুবিন্যস্ত সাব-অ্যারের বামদিকে দেইঃ

এখন সুবিন্যস্ত সাব-অ্যারে ইন্ডেক্স 0 থেকে ইন্ডেক্স 1 পর্যন্ত যাচাই করে এবং নতুন key হল ইন্ডেক্স 2 এ রয়েছে। আমরা এটিকে সুবিন্যস্ত সাব-অ্যারের বামে যোগ করিঃ

প্রতিটি অ্যারের উপাদানকে key হিসেবে বিবেচনা করে এবং বামদিকে যোগ করে এরকম প্রক্রিয়া চালাতে থাকিঃ

সবচেয়ে ডানদিকের উপাদান যখন যোগ করা হয়ে যায়, তখন অ্যারে সুবিন্যস্ত করা শেষ হয়ঃ

উদাহরণের কিছু ব্যাপার সম্পর্কে আরও জানা উচিত: যখন key তার বামের সকল উপাদান থেকে ছোট হয় (key 2 এবং 3 যোগ করার মত) এবং যখন key তার বামের সকল উপাদান থেকে বড় কিংবা সমান হয় (যেমন আমরা key 13 যোগ করেছিলাম)। পূর্বের ক্ষেত্রে, key এর বামের সকল উপাদান একবার করে ডানদিকে যায় এবং অ্যারের বামদিকের শেষ প্রান্তে আমাদের থামতে হয়। পরবর্তী ক্ষেত্রে, প্রথমে key এর সাথে বামদিকের উপাদানের তুলনা করার সময়, দেখায় যায় যে key এর বামের উপাদানগুলোর সাপেক্ষে সঠিক স্থানেই আছে; কোন উপাদান সরানোর দরকার নেই এবং key তার শুরুর-স্থানে থেকে যায়।

ইনসারশন সর্টের মূল ধাপ হল বর্তমান মানকে বসানোর জন্য অ্যারেতে জায়গা তৈরি করা, যা key চলকে সংরক্ষিত থাকে। যেমনটি আমরা উপরে দেখেছি, আমরা key এর শুরু স্থানের বামদিকে যাই, ডান থেকে বাম, প্রতিটি উপাদাকে সরাই যা key এর থেকে বড় এবং এক স্থান ডানে রয়েছে। যখন আমরা পাই যে উপাদানটি key থেকে ছোট, অথবা key এর সমান, সরানো বন্ধ করে key কে উপাদানের ডানদিকে ফাঁকা স্থানে যোগ করি। (অবশ্যই স্থানটি ফাঁকা নয়, শুধু ডানদিকে নেওয়া হয়।) নিচের চিত্রে ব্যাখ্যা দেওয়া হল:

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