র‍্যান্ডোমাইজড কুইকসর্ট ও এক্সপেক্টেড টাইম অ্যানালাইসিস

import random

def randomized_quicksort(rng, arr):
    arr = list(arr)
    def qs(lo, hi):
        if lo >= hi:
            return
        pivot_idx = rng.randint(lo, hi)          # র‍্যান্ডম পিভট -- একমাত্র পরিবর্তন L16-এর নেইভ সংস্করণ থেকে
        arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
        pivot = arr[hi]
        store = lo
        for i in range(lo, hi):
            if arr[i] < pivot:
                arr[i], arr[store] = arr[store], arr[i]
                store += 1
        arr[store], arr[hi] = arr[hi], arr[store]
        qs(lo, store - 1)
        qs(store + 1, hi)
    qs(0, len(arr) - 1)
    return arr

# প্রথমেই সঠিকতা যাচাই -- এটি এখনো একটি লাস ভেগাস অ্যালগরিদম (L53), তাই আউটপুট সবসময় সঠিক হতে হবে
master_rng = random.Random(2026)
all_correct = True
for trial in range(25):
    n = master_rng.randint(1, 60)
    test_arr = [master_rng.randint(-50, 50) for _ in range(n)]
    seed = master_rng.randint(0, 10**6)
    sort_rng = random.Random(seed)
    result = randomized_quicksort(sort_rng, test_arr)
    if result != sorted(test_arr):
        all_correct = False
        print(f"trial {trial}: MISMATCH!")

print(f"২৫টি র‍্যান্ডম টেস্টে (বিভিন্ন n, বিভিন্ন seed) randomized quicksort সবসময় সঠিক ফলাফল দিয়েছে: {all_correct}")
assert all_correct

import random
import math

def naive_quicksort_count(arr):
    # L16-এর ফিক্সড-পিভট সংস্করণ (সবসময় শেষ এলিমেন্ট) -- comparison counter সহ
    arr = list(arr)
    comparisons = [0]
    def qs(lo, hi):
        if lo >= hi:
            return
        pivot = arr[hi]
        store = lo
        for i in range(lo, hi):
            comparisons[0] += 1
            if arr[i] < pivot:
                arr[i], arr[store] = arr[store], arr[i]
                store += 1
        arr[store], arr[hi] = arr[hi], arr[store]
        qs(lo, store - 1)
        qs(store + 1, hi)
    qs(0, len(arr) - 1)
    return comparisons[0]

def randomized_quicksort_count(rng, arr):
    # ঠিক একই লজিক, শুধু পিভট এখন র‍্যান্ডম -- comparison counter সহ
    arr = list(arr)
    comparisons = [0]
    def qs(lo, hi):
        if lo >= hi:
            return
        pivot_idx = rng.randint(lo, hi)
        arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
        pivot = arr[hi]
        store = lo
        for i in range(lo, hi):
            comparisons[0] += 1
            if arr[i] < pivot:
                arr[i], arr[store] = arr[store], arr[i]
                store += 1
        arr[store], arr[hi] = arr[hi], arr[store]
        qs(lo, store - 1)
        qs(store + 1, hi)
    qs(0, len(arr) - 1)
    return comparisons[0]

sizes = [50, 100, 200, 400]
num_seeds = 40

print(f"{'n':>5} | {'নেইভ (আগে-সাজানো, L16)':>24} | {'র‍্যান্ডোমাইজড গড়':>18} | {'গড়/(n·log2 n)':>15}")
naive_counts = []
rand_avgs = []
rand_samples_by_n = {}
for n in sizes:
    sorted_arr = list(range(n))     # L16-এর ঠিক সেই adversarial ইনপুট -- ইতিমধ্যে সম্পূর্ণ সাজানো

    naive_c = naive_quicksort_count(sorted_arr)
    naive_counts.append(naive_c)

    samples = []
    for seed in range(num_seeds):
        rng = random.Random(seed)   # প্রতিটি ট্রায়ালের জন্য একটি ভিন্ন, কিন্তু নির্দিষ্ট (reproducible) seed
        samples.append(randomized_quicksort_count(rng, sorted_arr))
    rand_samples_by_n[n] = samples
    avg = sum(samples) / len(samples)
    rand_avgs.append(avg)

    ratio = avg / (n * math.log2(n))
    print(f"{n:>5} | {naive_c:>24} | {avg:>18.1f} | {ratio:>15.3f}")

print("\nn দ্বিগুণ হলে বৃদ্ধির অনুপাত (nাইভ ~4x হওয়া উচিত -- Theta(n^2); randomized ~2x-এর কাছাকাছি -- Theta(n log n)):")
for i in range(1, len(sizes)):
    n_prev, n_cur = sizes[i - 1], sizes[i]
    print(f"n={n_prev}->{n_cur}: নেইভ {naive_counts[i]/naive_counts[i-1]:.2f}x, "
          f"র‍্যান্ডোমাইজড গড় {rand_avgs[i]/rand_avgs[i-1]:.2f}x")

biggest_n = sizes[-1]
biggest_samples = rand_samples_by_n[biggest_n]
print(f"\nn={biggest_n}-এ {num_seeds}টি ভিন্ন seed-এর মধ্যে তুলনার সংখ্যার তারতম্য:")
print(f"সর্বনিম্ন: {min(biggest_samples)}, সর্বোচ্চ: {max(biggest_samples)}, গড়: {sum(biggest_samples)/len(biggest_samples):.1f}")
print(f"(তুলনা করুন নেইভের নিশ্চিত {naive_counts[-1]} তুলনার সাথে -- randomized-এর যেকোনো একক ট্রায়ালও অনেক কম)")

assert rand_avgs[-1] < naive_counts[-1] / 5, "র‍্যান্ডোমাইজড গড় প্রত্যাশার চেয়ে অনেক বেশি বড়!"