কুইক-সিলেক্ট (QuickSelect)
কল্পনা করুন আপনার কাছে একটি অগোছালো বুকশেলফ বা বইয়ের তাক আছে এবং আপনি ৫ম সবচেয়ে ছোট বইটি খুঁজছেন। এর জন্য আপনার পুরো তাকের সব বই উচ্চতা অনুযায়ী সাজানোর দরকার নেই — আপনার শুধু ৫ম সবচেয়ে ছোট বইটি দরকার। সবকিছু সাজানো এক্ষেত্রে অযথাই সময় নষ্ট করা।
কুইক-সিলেক্ট (QuickSelect) অনেক বেশি বুদ্ধিমান। যেকোনো একটি বইকে পিভট (pivot) হিসেবে বেছে নিন। এর চেয়ে ছোট সব বই বাঁয়ে সরান, এবং লম্বা সব বই ডানে। এখন পিভটটি সাজানো অবস্থায় এর চূড়ান্ত জায়গায় গিয়ে পৌঁছাল। যদি সেই অবস্থানটি ঠিক ৪ হয় (যেহেতু ০-ভিত্তিক ইনডেক্স, তাই এটি ৫ম ছোট বই) — তাহলে কাজ শেষ! যদি এর অবস্থান ৭ হয়, তবে আপনার শুধু বাঁ দিকের অংশটুকু খুঁজলেই হবে। আর যদি অবস্থান ২ হয়, তবে শুধু ডান দিকে খুঁজতে হবে। প্রতিটি ধাপে, আপনি আপনার অপ্রয়োজনীয় অর্ধেক অংশটি বাদ দিয়ে দিচ্ছেন বা ফেলে দিচ্ছেন।
কুইক সর্ট থেকে প্রধান পার্থক্য
কুইক সর্ট (QuickSort) উভয় অর্ধাংশে রিকার্শন প্রয়োগ করে — কারণ এর সবকিছু সাজানো দরকার। অন্যদিকে কুইক-সিলেক্ট যেকোনো এক অর্ধাংশে রিকার্শন প্রয়োগ করে — ঠিক যে দিকে k-তম উপাদানটি রয়েছে। অন্য অর্ধেকটি পুরোপুরি এড়িয়ে যাওয়া হয়। আর এ কারণেই এটির গড় সময় \(O(n \log n)\) থেকে কমে \(O(n)\) হয়ে যায়।
এর গণিত যেভাবে কাজ করে
একটি র্যান্ডম পিভট গড়ে মাঝামাঝি কোথাও পড়ে, যা প্রতিবার অ্যারেটিকে প্রায় সমান দুই ভাগে ভাগ করে দেয়। এক্ষেত্রে মোট কাজের পরিমাণ দাঁড়ায়: n + n/2 + n/4 + n/8 + … এটি একটি জিওমেট্রিক সিরিজ (geometric series) যার যোগফল 2n — তাই প্রত্যাশিত বা এক্সপেক্টেড (expected) মোট কাজের পরিমাণ হলো \(O(n)\)।
সবচেয়ে খারাপ ক্ষেত্র বা ওয়ার্স্ট কেস (The worst case)
যদি প্রতিবারই বাজে বা খারাপ পিভট বেছে নেওয়া হয় (সবসময় সবচেয়ে ছোট বা সবচেয়ে বড় উপাদানটি), তবে আমরা প্রতি ধাপে মাত্র একটি করে উপাদান বাদ দিতে পারব। মোট কাজের পরিমাণ: n + (n-1) + (n-2) + … = \(O(n^2)\) — সাজানো বা সর্টেড ইনপুটের ক্ষেত্রে কুইক সর্টের যেমন দশা হয় ঠিক তেমনি।
এর সমাধান: পিভটটি র্যান্ডমভাবে (randomly) বা দৈবচয়নের মাধ্যমে বেছে নিন। একটি র্যান্ডম পিভট এমন বিপর্যয়কর অবস্থার সম্ভাবনাকে প্রায় অসম্ভব করে তোলে। তবে আপনার যদি নিশ্চিতভাবে (guaranteed) \(O(n)\) ওয়ার্স্ট কেস প্রয়োজন হয় (যেমন, ক্ষতিকর বা অ্যাডভারসারিয়াল ইনপুট বা adversarial inputs আটকাতে), তবে মিডিয়ান অফ মিডিয়ানস (Median of Medians) ব্যবহার করুন — যদিও এতে কনস্ট্যান্ট ফ্যাক্টর (constant factor) একটু বেড়ে যায়।