কুইক সর্ট ও পিভট সিলেকশন

১ · কুইক সর্ট — সংক্ষিপ্ত রিক্যাপ

কুইক সর্টের মেকানিক্স ইতিমধ্যে DSA কোর্সে কভার করা হয়েছে: একটি পিভট বেছে অ্যারেকে পিভটের চেয়ে ছোট ও বড় — এই দুই ভাগে পার্টিশন করা হয় (ডিভাইড ধাপেই আসল কাজ, L14 দ্রষ্টব্য), তারপর প্রতিটি ভাগ রিকার্সিভভাবে সর্ট করা হয় (কমবাইন ধাপে কিছুই করার নেই)। এই পাঠে মেকানিক্স নয়, বরং পিভট কীভাবে বাছাই করা হচ্ছে তার উপর জটিলতা কতটা নির্ভরশীল তা বিশ্লেষণ করা হবে।

২ · ওয়ার্স্ট কেস — $\Theta(n^2)$

ধরা যাক পিভট বাছাইয়ের নিয়মটি নেইভ ও ফিক্সড — প্রতিবার সবসময় শেষ এলিমেন্টকে পিভট হিসেবে নেওয়া হয় (বা সমতুল্যভাবে, সবসময় প্রথম এলিমেন্ট)। এখন ইনপুট যদি ইতিমধ্যে ঊর্ধ্বক্রমে সর্টেড থাকে, তাহলে প্রতিটি পার্টিশনে পিভট (শেষ এলিমেন্ট) সেই সাব-অ্যারের সর্বোচ্চ মান — অর্থাৎ বাকি সব এলিমেন্টই পিভটের চেয়ে ছোট, ফলে পার্টিশন সম্পূর্ণ অসামঞ্জস্যপূর্ণ হয়: একটি ভাগে $n-1$টি এলিমেন্ট, অন্য ভাগে $0$টি।

প্রতিটি পার্টিশন ধাপে $O(n)$ সময় লাগে (পুরো সাব-অ্যারে একবার স্ক্যান করতে হয়), এবং প্রতিবার সমস্যার আকার মাত্র $1$ কমে। তাই রিকারেন্স:

এটি সরাসরি সমষ্টি (summation) আকারে খুলে ফেলা যায়:

এবং যেহেতু প্রতিটি পদই ধনাত্মক ও নিচের দিকেও একই আর্গুমেন্ট প্রযোজ্য (প্রতিটি পার্টিশনে অন্তত $\Omega(n-i)$ কাজ হয়), তাই আসলে $T(n) = \Theta(n^2)$ — শুধু আপার বাউন্ড নয়, টাইট বাউন্ড। মনে রাখবেন, এই একই রিকারেন্স ফর্ম $T(n) = T(n-1) + O(n)$ M3-এর সাবস্টিটিউশন বা রিকার্সন ট্রি মেথড দিয়েও একই ফলাফলে পৌঁছায় (মাস্টার থিওরেম সরাসরি প্রযোজ্য নয় এখানে, কারণ সাব-প্রবলেমগুলোর আকার সমান ভাগে ভাগ হয় না — $a=1$ কিন্তু $b$ ধ্রুবক নয়)।

৩ · অ্যাভারেজ কেস — $\Theta(n \log n)$

এখন একই ফিক্সড-পিভট কুইক সর্ট যদি একটি র‍্যান্ডম ক্রমে সাজানো ইনপুটে চালানো হয়, তাহলে পিভট (শেষ এলিমেন্ট) হওয়ার সম্ভাবনা প্রতিটি র‍্যাংকের জন্য সমান — অর্থাৎ পিভট কখনো সবচেয়ে ছোট/বড় হতে পারে (খারাপ স্প্লিট), কিন্তু বেশিরভাগ সময় এটি মাঝামাঝি কোনো র‍্যাংকে পড়ে (মোটামুটি সুষম স্প্লিট)। যদি প্রতিটি পার্টিশন অন্তত একটি ধ্রুবক ভগ্নাংশ (যেমন ২৫%/৭৫% স্প্লিটও) অনুপাতে হয়, তাহলে রিকার্সনের গভীরতা তখনও $O(\log n)$ থাকে (L13-এর "অসম কিন্তু ধ্রুবক-ভগ্নাংশ" স্প্লিট আলোচনার মতো) — ফলাফল $\Theta(n \log n)$।

এই আর্গুমেন্টটি এখানে ইনটুইশন স্তরে রাখা হচ্ছে ইচ্ছাকৃতভাবে — একটি সম্পূর্ণ রিগোরাস প্রমাণ (এক্সপেক্টেড তুলনার সংখ্যা ইনডিকেটর ভ্যারিয়েবল ও লিনিয়ারিটি অফ এক্সপেক্টেশন দিয়ে গণনা) দাবি করে যে পিভট র‍্যান্ডমভাবে বাছাই করা হচ্ছে, ইনপুট নয় (কারণ ইনপুট সবসময় "র‍্যান্ডম" হবে এই ধরে নেওয়া নিরাপদ নয়!) — এটাই M12/L54 (র‍্যান্ডোমাইজড কুইকসর্ট)-এর বিষয়, যা এই ওয়ার্স্ট-কেস দুর্বলতার রিগোরাস সমাধান দেয়: প্রতিবার পিভট এলোমেলোভাবে বাছাই করে, যেকোনো নির্দিষ্ট ইনপুট (এমনকি সর্টেড) আর আলাদাভাবে খারাপ থাকে না, এবং প্রত্যাশিত (expected) রানটাইম সবসময় $\Theta(n \log n)$ প্রমাণ করা যায়।

৪ · কম্পিউটেশনাল ডেমো — একই কোড, দুই ইনপুট

নিচের কোডে একটি নেইভ ফিক্সড-পিভট (সবসময় শেষ এলিমেন্ট) কুইক সর্ট ইমপ্লিমেন্ট করা হয়েছে, যা তুলনার সংখ্যা গুনে রাখে। এটি একবার সর্টেড ইনপুটে (ওয়ার্স্ট কেস) এবং একবার র‍্যান্ডম ইনপুটে (অ্যাভারেজ কেস) চালানো হয়েছে — একই কোড, শুধু ইনপুট ভিন্ন।

import random
import math
import sys

sys.setrecursionlimit(3000)

def quicksort_counted(arr):
    """নেইভ ফিক্সড-পিভট (সবসময় শেষ এলিমেন্ট) কুইক সর্ট — তুলনার সংখ্যা গুনে রাখে।"""
    a = list(arr)
    counter = [0]

    def partition(lo, hi):
        pivot = a[hi]  # নেইভ ফিক্সড পিভট
        i = lo - 1
        for j in range(lo, hi):
            counter[0] += 1
            if a[j] <= pivot:
                i += 1
                a[i], a[j] = a[j], a[i]
        a[i + 1], a[hi] = a[hi], a[i + 1]
        return i + 1

    def sort(lo, hi):
        if lo < hi:
            p = partition(lo, hi)
            sort(lo, p - 1)
            sort(p + 1, hi)

    sort(0, len(a) - 1)
    return a, counter[0]

random.seed(42)
sizes = [50, 100, 200, 400]
results = []

for n in sizes:
    sorted_input = list(range(n))
    sorted_result, c_sorted = quicksort_counted(sorted_input)
    assert sorted_result == sorted(sorted_input)

    random_input = list(range(n))
    random.shuffle(random_input)
    random_result, c_random = quicksort_counted(random_input)
    assert random_result == sorted(random_input)

    results.append((n, c_sorted, c_random))

print(f"{'n':>5} | {'সর্টেড ইনপুট (worst)':>22} | {'র‍্যান্ডম ইনপুট (avg)':>22} | {'n(n-1)/2':>10} | {'n*log2(n)':>10}")
for n, c_sorted, c_random in results:
    worst_predicted = n * (n - 1) // 2
    avg_predicted = n * math.log2(n)
    print(f"{n:>5} | {c_sorted:>22} | {c_random:>22} | {worst_predicted:>10} | {avg_predicted:>10.1f}")

print("\nn দ্বিগুণ হলে তুলনার সংখ্যা কত গুণ বাড়ে:")
for i in range(1, len(results)):
    n_prev, cs_prev, cr_prev = results[i - 1]
    n_cur, cs_cur, cr_cur = results[i]
    print(f"n={n_prev}->{n_cur}: সর্টেড ইনপুটে {cs_cur / cs_prev:.2f}x, র‍্যান্ডম ইনপুটে {cr_cur / cr_prev:.2f}x বেড়েছে")