Sorting Benchmark Lab

কেন এই প্রজেক্ট

Sorting লেসনে প্রতিটা algorithm-এর big-O মুখস্থ হয়ে গেছে — insertion O(n²), merge O(n log n), quick average O(n log n) কিন্তু worst O(n²)। Asymptotic-analysis লেসনে দেখেছি constant factor বড় n-এ অদৃশ্য হয়। কিন্তু দুটো প্রশ্ন কোথাও উত্তর হয়নি:

1. Sorted input-এ naive quicksort কীভাবে O(n²)-এ নেমে আসে, stack overflow পর্যন্ত যায় — সেটা চোখে দেখা?
2. Nearly-sorted data-তে “ধীর” insertion sort কেন আসল জগতে জিতে যায়?

এই প্রজেক্টে measurement-ই প্রধান কাজ — algorithm লেখা মাত্র ৩০%। যেকোনো performance claim ভবিষ্যতে করার আগে এই প্রজেক্ট শেখাবে প্রথমে জিজ্ঞেস করতে: warmup হলো? median নিয়েছেন? input distribution কী?

ধাপে ধাপে

১. চারটা sort

def insertion_sort(a):
    for i in range(1, len(a)):
        x = a[i]
        j = i - 1
        while j >= 0 and a[j] > x:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    return _merge(left, right)          # stable merge: tie-তে left আগে

def quick_sort(a, lo=0, hi=None):       # random pivot — naive first-pivot নয়
    if hi is None: hi = len(a) - 1
    while lo < hi:
        p = _partition_random(a, lo, hi)
        if p - lo < hi - p:
            quick_sort(a, lo, p - 1); lo = p + 1     # ছোট দিক recurse
        else:
            quick_sort(a, p + 1, hi); hi = p - 1     # বড় দিক loop

Quicksort-এ ছোট partition recurse, বড়টা tail-loop — worst-case stack depth O(log n)। Heapsort Heap-priority-queues-এর sift_down পুনর্ব্যবহার করে in-place লিখুন।

২. Input generators

import random

def gen(kind, n, rng=random.Random(7)):
    base = list(range(n))
    if kind == 'random':      rng.shuffle(base); return base
    if kind == 'sorted':      return base
    if kind == 'reversed':    return base[::-1]
    if kind == 'duplicates':  return [rng.randrange(max(2, n // 10)) for _ in range(n)]
    if kind == 'nearly':      # 95% sorted, 5% local shuffle
        for i in range(0, n, 20):
            rng.shuffle(base[i:i+3])
        return base

Seed fixed — reproducibility benchmark-এর প্রাণ। Duplicates keyspace ছোট রাখুন যাতে 3-way partition না করলে quicksort কষ্ট পায়; nearly- sorted হলো real-world data-র proxy (log file, database index)।

৩. Timing harness

import time, gc, statistics

def bench(fn, data, repeats=5, warmup=1):
    for _ in range(warmup):              # allocator, cache গরম করুন
        fn(list(data))
    times = []
    for _ in range(repeats):
        work = list(data)                # প্রতি run-এ fresh copy
        gc.collect(); gc.disable()
        t0 = time.perf_counter()
        fn(work)
        times.append(time.perf_counter() - t0)
        gc.enable()
    assert work == sorted(data)          # correctness gate — সময় নয়, ঠিক আছে কি?
    return statistics.median(times)

তিনটা জিনিস non-negotiable: perf_counter (monotonic, high-resolution, wall clock), warmup run (প্রথম run-এ allocator আর page fault), আর median — mean-এ GC pause বা scheduler preemption outlier ঢুকে টেবিল নষ্ট করে। Correctness assertion প্রতি run-এ — গরম অবস্থায় ভুল sort চালিয়ে সুন্দর সংখ্যা জমানোর দিন নেই।

৪. Theory-vs-wallclock report

n = 2k, 8k, 32k তিন সাইজে চালিয়ে টেবিল:

algorithm	random	sorted	reversed	dup	near-sorted
insertion	…	…	…	…	…
merge	…	…	…	…	…
quick	…	…	…	…	…
heap	…	…	…	…	…

তারপর theory check: n দ্বিগুণ হলে merge/quick/heap-এর সময় কি ×2 এর চেয়ে সামান্য বেশি (n log n অনুযায়ী), insertion random-এ কি ×4-এর কাছে (n²)? মিললো asymptotic class প্রমাণিত। যেখানে মিলবে না সেটাই আসল উপহার — sorted input-এ insertion linear-এ চলে, theory table-এর O(n²) label সেখানে misleading; best case আর worst case আলাদা কথা।

Naive quicksort-ও এক লাইনে রাখুন (pivot = a[lo]) আর sorted/reversed column-এ চালান — O(n²) blowup আর recursion limit crash দুটোই দর্শক।

৫. Stability checker

def is_stable(sort_fn):
    pairs = [(i // 3, f'v{i}') for i in range(300)]   # key-তে 100 distinct, payload unique
    out = sort_fn(pairs[:], key=lambda p: p[0])
    for k in range(len(out) - 1):
        if out[k][0] == out[k+1][0] and out[k][1] > out[k+1][1]:
            return False
    return True

Stable মানে equal key-তে original order টিকে। Merge sort stable (tie-তে left half আগে), heapsort stable না (sift দূরের element এনে বসায়), quicksort partition scheme-এর উপর নির্ভর করে। Checker-টা generic রাখুন — Python-এর sorted-ও একই harness-এ চালিয়ে মিলান।

Checkpoint: আপনার চার sort-এর stability verdict checker-এর সঙ্গে textbook-এর সঙ্গে — তিন জায়গায় এক।

৬. Findings template

FINDINGS.md-এ প্রশ্ন ছাপানো থাকবে, আপনি সংখ্যা বসাবেন:

1. Nearly-sorted 10k-তে insertion vs merge — কত গুণ, কেন? (inversion count-এর সঙ্গে runtime-এর সম্পর্ক)
2. Random 100k-তে quick vs heap — দুজনেই O(n log n), gap কেন? (memory access pattern, branch prediction, cache locality)
3. Duplicate-heavy-তে কোন sort collapse করে, 3-way partition কত বাঁচায়?
4. সবশেষে মূল প্রশ্ন — কেন timsort জেতে: এটা নতুন algorithm নয়, adaptive hybrid — input-এ natural run (already-sorted streak) খুঁজে insertion sort দিয়ে extend করে, তারপর merge; nearly-sorted-এ practically O(n), আর stable-ও। আপনার টেবিলের near-sorted column আর stability checker-ই এই claim-এর evidence।

নিজেকে চ্যালেঞ্জ করুন

1. Radix sort (LSD, counting-sort pass) — fixed-width integer-এ O(n) প্রমাণ করুন টেবিলে
2. Bottom-up (iterative) merge sort — allocation অর্ধেক, মাপুন কতটা বাঁচলো
3. Dual-pivot quicksort (Java-র পদ্ধতি) বনাম single pivot
4. Small-array cutoff — সাবarray 16-এর নিচে হলে insertion sort; threshold sweep করে optimum বের করুন
5. Branchless partition — conditional move কৌশলে comparison কমানো
6. Parallel merge — multiprocessing pool দিয়ে halves, overhead-র break-even size মাপুন

যা এখানে শিখলেন, পরে যেখানে লাগবে

এখানে	পরে
Warmup + median methodology	DS Library প্রজেক্টের benchmark harness — একই discipline
Input distribution sensitivity	Database query planner — data statistics ছাড়া plan ভুল
Stability-র practical মানে	Multi-key sort (SQL ORDER BY a, b) ঠিক stable sort দিয়ে চলে
Adaptive algorithm-এর idea	timsort, introsort — production library-র ডিজাইন philosophy
Theory-vs-measured gap	Performance engineering — claim প্রতিটা মাপা সংখ্যায়