ডেটা স্ট্রাকচরে অ্যাডাপ্টিভ মার্জিং এবং সর্টিং

অ্যাডাপ্টিভ মার্জ সর্ট (ADAPTIVE MERGE SORT)

অ্যাডাপ্টিভ মার্জ সর্ট সর্টেড সাব-লিস্ট মার্জ করে যা মার্জ সর্ট করে। তবে, ইনিশিয়াল সাব-লিস্টের সাইজ নির্ভর করে এলিমেন্টের মাঝপথে অর্ডারিং এর একজিস্টেন্সের ওপর বদলে সাব-লিস্ট সাইজ ১'avoir। উদাহরণস্বরূপ, ফিগারের লিস্টটি বিবেচনা করুন।

এতে ২টি সর্টেড সাব-লিস্ট আছে।

• সাব-লিস্ট ১ এলিমেন্ট ১৬,১৫,১৪,১৩ সহ।
• সাব-লিস্ট ২ এলিমেন্ট ৯,১০,১১,১২ সহ।

সাব-লিস্ট ১ সর্টেড কিন্তু রিভার্স অর্ডারে। তাই সাব-লিস্ট ১ রিভার্স করা হয় ফিগার দেখানো।

সাব-লিস্টগুলো একবার পাওয়া গেলে মার্জিং প্রসেস শুরু হয়। অ্যাডাপ্টিভ মার্জ সর্ট সাব-লিস্টগুলো মার্জ করা শুরু করে। অ্যাডাপ্টিভ মার্জ সর্টকে শুধু এক মার্জিং স্টেপ লাগবে কারণ শুধু ২টি সাব-লিস্ট আছে। মার্জিংয়ের ফলাফল ফিগার-এ দেখানো হলো।

ডিজাইন আইডিয়া (Design Idea)

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

অ্যাডাপ্টিভ মার্জ সর্ট অ্যানালিসিস (Adaptive Merge Sort Analysis)

অ্যাডাপ্টিভ মার্জ সর্ট সাব-লিস্ট সাইজ ১ দিয়ে শুরু না করে, সাব-লিস্ট খুঁজে বের করে যারা ইতিমধ্যে সর্টেড আছে রিকোয়ার্ড বা রিভার্স অর্ডারে। ইনিশিয়ালি পাওয়া সাব-লিস্টের সাইজ কমপক্ষে ২ এবং সর্বোচ্চ m (m হলো এলিমেন্টের সংখ্যা)।

তবে, যদি সাব-লিস্টে রিভার্স অর্ডারে এলিমেন্ট থাকে, তবে মার্জ অপারেশন শুরু করার আগে লিস্টটি রিভার্স করে। লিস্ট রিভার্সের জন্য (m/2) এক্সচেঞ্জ অপারেশন লাগে।

বেস্ট কেস (Best Case)

যদি লিস্ট ইতিমধ্যে সর্টেড অর্ডারে বা রিভার্স অর্ডারে থাকে, তবে অ্যাডাপ্টিভ মার্জ সর্টের শুধু একটি লিস্ট থাকবে এবং কোনো মার্জ অপারেশন দরকার নেই। যাইহোক, লিস্টটি ইতিমধ্যে সর্টেড আছে কিনা খুঁজে বের করতে O(m) কমপেয়ারিজন অপারেশন এবং (m/2) এক্সচেঞ্জ অপারেশন লাগবে যদি লিস্ট রিভার্স সর্টেড থাকে। এতে অ্যাডাপ্টিভ মার্জ সর্ট অ্যাডাপ্টিভ হয় এমনকি লিস্ট রিভার্স সর্টেড থাকলে।

সুতরাং বেস্ট কেসের জন্য টাইম কমপ্লেক্সিটি নিচের মতো ক্যালকুলেট করা হয় −

T(m) = (m-1)+(m/2) T(m) = (2m-2+m)/2 T(m) = O(m).

তবে, অ্যাডাপ্টিভ মার্জ সর্ট মার্জ সর্টের চেয়ে O(m) অ্যাডিশনাল স্পেস বাস্তবায়ন করে।

ওয়ার্স্ট কেস (Worst Case)

অ্যাডাপ্টিভ মার্জ সর্ট সাব-লিস্ট খুঁজে বের করে যেটি ইতিমধ্যে সর্টেড আছে রিকোয়ার্ড বা রিভার্স অর্ডারে। তবে, ওয়ার্স্ট কেসে কোনো পার্শিয়াল বা টোটাল অর্ডারিং এলিমেন্ট নেই। তাই, ইনিশিয়ালি পাওয়া সাব-লিস্ট সাইজ ২ হবে। একবার সাব-লিস্টগুলো পাওয়া গেলে মার্জিং প্রসেস শুরু হয়।

• সাইজ ২ সাব-লিস্ট মার্জ করলে সর্টেড সাব-লিস্ট সাইজ ৪ হয়।
• সাইজ ৪ সাব-লিস্ট মার্জ করলে সর্টেড সাব-লিস্ট সাইজ ৮ হয়।
• মার্জিং প্রসেস চলতে থাকে যতক্ষণ না 2k < m। যেখানে k হলো kth মার্জিং স্টেপ।

যেহেতু অ্যাডাপ্টিভ মার্জ সর্টের ওয়ার্স্ট কেসে মার্জিং স্টেপস মার্জ সর্টের মতোই। তাই অ্যাডাপ্টিভ মার্জ সর্টের ওয়ার্স্ট কেসের টাইম কমপ্লেক্সিটি মার্জ সর্টের মতোই −

T(m) = O(m log m).