র‍্যান্ডমাইজড কুইক সর্ট (Randomized Quick Sort)

কল্পনা করুন আপনাকে উচ্চতা অনুযায়ী ১০০ জনকে সাজাতে হবে। আপনি দল থেকে একজনকে রেফারি (referee) হিসেবে বেছে নিলেন। তার চেয়ে খাটো সবাই তার বাঁ দিকে দাঁড়াবে, আর লম্বা সবাই ডান দিকে দাঁড়াবে। তারপর আপনি প্রতিটি অর্ধেকের জন্য এই একই কাজ পুনরাবৃত্তি (recursively) করবেন।

যদি রেফারির উচ্চতা মোটামুটি মাঝামাঝি হয়, তবে প্রতিটি অর্ধে প্রায় ৫০ জন করে থাকবে — এবং প্রতিটি ধাপে কাজ চমৎকারভাবে অর্ধেক হয়ে যাবে: মোট O(n log n)। কিন্তু আপনি যদি সবসময় সবচেয়ে লম্বা মানুষটিকে রেফারি হিসেবে বেছে নেন, তবে একপাশে ৯৯ জন এবং অন্যপাশে ০ জন থাকবে — এটি সময়ের সাথে O(n²) আচরণ করবে।

এর সমাধান খুব সহজ: রেফারিকে এলোমেলোভাবে (randomly) বেছে নিন। একজন র‍্যান্ডম ব্যক্তির সবচেয়ে লম্বা বা সবচেয়ে খাটো হওয়ার সম্ভাবনা নেই বললেই চলে। আর যদি একবার এমন দুর্ভাগ্যজনক বাছাই হয়েও যায়, তবে রিকার্শনের পরবর্তী স্তরে আবার নতুন করে র‍্যান্ডম বাছাই হবে — প্রতিটি বাছাইয়ে খারাপ ফলাফল হওয়ার সম্ভাবনা সূচকীয় হারে (exponentially) কমতে থাকে।

কেন ডিটারমিনিস্টিক কুইক সর্ট সাজানো ইনপুটে ব্যর্থ হয়

চিরায়ত বাগ (classic bug): প্রতিবার শেষ উপাদানটিকে পিভট হিসেবে বেছে নেওয়া। [1, 2, 3, 4, 5] এর মতো আগে থেকেই সাজানো (sorted) অ্যারেতে, শেষ উপাদানটি সবসময়ই সর্বোচ্চ হয়। প্রতিটি বিভাজন (partition) চরমভাবে ভারসাম্যহীন হয়: একপাশে ০টি উপাদান থাকে, অন্যপাশে n-1 টি। আপনি n সংখ্যক রিকার্শন স্তর পাবেন, যার প্রতিটি O(n) কাজ করে — মোট দ্বিঘাত (quadratic) সময়।

এটি কেবল একটি তাত্ত্বিক সমস্যা নয়। একটি সাজানো বা প্রায়-সাজানো তালিকাকে সর্ট করা বাস্তব জগতে খুবই সাধারণ একটি কাজ। অনেক সিস্টেম কুইক সর্টে সাজানো ডেটা দেয় এবং অবাক হয় যে এটি এত ধীরগতিতে কেন চলছে।

র‍্যান্ডম পিভট: কোনো ইনপুটই প্রতিকূল হতে পারে না

র‍্যান্ডম পিভটের সাথে, কোনো নির্দিষ্ট ইনপুট সবচেয়ে খারাপ ক্ষেত্রের (worst-case) আচরণ তৈরি করতে পারে না। O(n²) এ বাধ্য করার জন্য, প্রতিপক্ষকে (adversary) আপনার রিকার্শনের প্রতিটি স্তরে র‍্যান্ডম পছন্দগুলো অনুমান করতে হবে — যা তারা করতে পারে না। সবচেয়ে খারাপ ক্ষেত্রটি ডেটার উপর নির্ভর না করে আপনার র‍্যান্ডম নম্বর জেনারেটরের ফাংশনে পরিণত হয়।

প্রত্যাশিত তুলনার বিশ্লেষণ (The Expected Comparisons Analysis)

ধরুন X_{ij} = 1 যদি সাজানো র‍্যাঙ্ক i এবং j এর উপাদানগুলো কখনো সরাসরি তুলনা করা হয়। দুটি উপাদানের তখনই তুলনা হয় যখন তাদের একটি পিভট হয় এবং উভয়েই একই সাব-অ্যারেতে থাকে। এর সম্ভাবনা কত? ঠিক 2 / (j − i + 1) — কারণ সাজানো ক্রমে তাদের মধ্যে j-i+1 টি উপাদান রয়েছে, এবং তুলনাটি কেবল তখনই ঘটবে যদি প্রথমে i বা j কে পিভট হিসেবে বেছে নেওয়া হয়।

সব জোড়ার যোগফল: E[তুলনা] = Σ 2/(j-i+1) ≈ 2n·ln(n) = O(n log n)। এটি উন্মুক্ত যেকোনো ইনপুটের জন্য কাজ করে।

ইন্ট্রোসর্ট (Introsort): উভয়ের সেরা দিক

বাস্তব-জগতের সর্ট ইমপ্লিমেন্টেশনগুলো (যেমন: C++ std::sort, Rust এর sort_unstable) ইন্ট্রোসর্ট (introsort) ব্যবহার করে: র‍্যান্ডমাইজড কুইক সর্ট দিয়ে কাজ শুরু করে কিন্তু রিকার্শনের গভীরতা পর্যবেক্ষণ করে। যদি গভীরতা 2·log n ছাড়িয়ে যায় — যা ধারাবাহিকভাবে খারাপ পিভটের লক্ষণ — তবে এটি হিপ সর্টে (HeapSort) চলে যায়, যা O(n log n) সবচেয়ে খারাপ ক্ষেত্রের গ্যারান্টি দেয়। এটি কুইক সর্টের চমৎকার ক্যাশ পারফরম্যান্সের সাথে নিখুঁত সবচেয়ে খারাপ ক্ষেত্রের গ্যারান্টি যুক্ত করে।