Quick sort, pivot আর quickselect

১ · মূল চিন্তা — একজনকে মাপকাঠি ধরে দুই দলে ভাগ

স্কুলের মাঠে পিটি-র ক্লাস। স্যার চান ৪০ জন ছাত্র উচ্চতা অনুযায়ী এক লাইনে দাঁড়াক। সবাইকে একে একে সবার সাথে মাপার বদলে তিনি একটি চালাক কাজ করলেন: একজন ছাত্রকে — ধরুন রাফিকে — মাঝখানে দাঁড় করালেন, আর বললেন, “রাফির চেয়ে খাটো সবাই বাঁ দিকে, লম্বা সবাই ডান দিকে।” এক মিনিটে দুটি দল তৈরি। এখন রাফি ঠিক তার চূড়ান্ত জায়গায় দাঁড়িয়ে আছে — তার বাঁয়ে যতজন, সবাই খাটো; ডানে যতজন, সবাই লম্বা। বাঁ দলের ভেতরে আর ডান দলের ভেতরে একই কৌশল আবার চালালেই পুরো লাইন সাজানো হয়ে যাবে।

এটিই quick sort. যে উপাদানকে মাপকাঠি ধরা হয় তার নাম pivot (পিভট). অ্যালগরিদমের তিনটি ধাপ:

1. Pivot বাছাই: অংশটির কোনো একটি উপাদান।
2. Partition: অংশটিকে এমনভাবে সাজানো, যাতে pivot-এর বাঁয়ে সব ছোট (বা সমান), ডানে সব বড় (বা সমান) থাকে। Pivot তখন নিজের চূড়ান্ত ঘরে।
3. রিকার্শন: বাঁ অংশ আর ডান অংশকে আলাদাভাবে quick sort. একটি বা শূন্যটি উপাদানের অংশ আগে থেকেই সাজানো — সেটিই base case.

Pseudocode — quick sort (0-based, inclusive range lo..hi)

quicksort(A, lo, hi):
    if lo >= hi: return              // 0 or 1 element: already sorted
    p = partition(A, lo, hi)         // pivot ends at index p
    quicksort(A, lo, p - 1)          // everything here <= A[p]
    quicksort(A, p + 1, hi)          // everything here >= A[p]

এটি পর্ব ০৮-০৯-এর divide and conquer-এর আরেকটি রূপ, কিন্তু merge sort-এর (পর্ব ২১) ঠিক উল্টো ছাঁচে। Merge sort ভাগ করে চোখ বুজে — মাঝখান থেকে — আর আসল পরিশ্রম করে জোড়া দেওয়ার (merge) সময়। Quick sort পরিশ্রম করে ভাগ করার (partition) সময়, আর জোড়া দেওয়ার কোনো কাজই থাকে না: দুই ভাগ সাজানো হয়ে গেলে পুরো অ্যারে আপনাআপনি সাজানো, কারণ বাঁয়ের প্রতিটি উপাদান ডানের প্রতিটির চেয়ে ছোট বা সমান। এর একটি বড় সুবিধা — merge sort-এর মতো বাড়তি n ঘরের অ্যারে লাগে না, সব কাজ মূল অ্যারের ভেতরেই হয়।

২ · Lomuto partition — একদিকে চলা দুটি pointer

Partition কীভাবে করবেন, সেটিই quick sort-এর হৃদয়। প্রথম পদ্ধতিটি সহজ, আর Jon Bentley তাঁর Programming Pearls বইয়ে এটি জনপ্রিয় করার সময় কৃতিত্ব দেন Nico Lomuto-কে — তাই নাম Lomuto partition. Cormen ও সহলেখকদের বিখ্যাত বই (CLRS)-ও মূলত এটিই শেখায়।

নিয়ম: শেষ উপাদান A[hi] হলো pivot. একটি pointer i মনে রাখে “ছোট-অংশের” শেষ ঘর (শুরুতে lo − 1, অর্থাৎ ছোট-অংশ খালি). আরেকটি pointer j বাঁ থেকে ডানে প্রতিটি উপাদান একবার দেখে। A[j] ≤ pivot হলে i এক বাড়িয়ে A[i] আর A[j] swap — অর্থাৎ ছোট উপাদানটিকে ছোট-অংশের ঠিক পরের ঘরে টেনে আনা। শেষে pivot-কে A[i+1]-এ বসানো।

Pseudocode — Lomuto partition (0-based)

partition(A, lo, hi):
    pivot = A[hi]
    i = lo - 1                       // A[lo..i] holds elements <= pivot
    for j = lo .. hi-1:
        if A[j] <= pivot:
            i = i + 1
            swap A[i], A[j]
    swap A[i+1], A[hi]               // pivot moves to its final place
    return i + 1

অ্যারে [4, 7, 2, 6, 1, 8, 3, 5]-এ ধাপে ধাপে দেখুন। Pivot = 5.

কেন Lomuto ঠিক — একটি loop invariant

পর্ব ০৩-এর পদ্ধতিতে প্রমাণ করি। Invariant: for লুপের প্রতিটি ঘূর্ণনের শুরুতে —

• A[lo..i]-এর প্রতিটি উপাদান ≤ pivot;
• A[i+1..j−1]-এর প্রতিটি উপাদান > pivot;
• A[hi] = pivot, আর A[j..hi−1] এখনো দেখা হয়নি।

শুরু (initialization): i = lo − 1, j = lo — প্রথম দুটি অংশ খালি, তাই শর্ত দুটি ফাঁকা অর্থে সত্য। রক্ষা (maintenance): A[j] > pivot হলে শুধু j বাড়ে, আর A[j] বড়-অংশের শেষে যুক্ত হয় — invariant টিকে থাকে। A[j] ≤ pivot হলে i বাড়ে, আর A[i] (যা বড়-অংশের প্রথম উপাদান ছিল, অথবা বড়-অংশ খালি থাকলে A[j] নিজেই) A[j]-এর সাথে swap হয়: ছোট উপাদানটি ছোট-অংশের শেষে আসে, বড়টি বড়-অংশের শেষে যায় — আবার invariant সত্য। সমাপ্তি (termination): j = hi হলে সব উপাদান তিন অংশের কোনো একটিতে। শেষ swap pivot-কে ছোট-অংশ আর বড়-অংশের মাঝে বসায় — ঠিক যা partition-এর কথা ছিল। লুপ ঠিক hi − lo বার ঘোরে, প্রতিবার O(1) কাজ: সময় Θ(n), বাড়তি জায়গা O(1).

পুরো quick sort-এর শুদ্ধতা এবার induction দিয়ে আসে: partition-এর পর A[p] সঠিক ঘরে; induction hypothesis অনুযায়ী দুই পাশের ছোট অংশ দুটি সঠিকভাবে সাজানো হয়; আর বাঁয়ের সব ≤ A[p] ≤ ডানের সব — তাই পুরোটা সাজানো। এবার কোডে চালিয়ে প্রতিটি partition দেখুন:

#include <cstdio>
#include <vector>
#include <algorithm>
#include <initializer_list>
using namespace std;
long long comparisons = 0;
int maxDepth = 0, show = 1;                        // show: print each partition
int partition(vector<int>& a, int lo, int hi) {   // Lomuto: pivot = last element
    int pivot = a[hi], i = lo - 1;                 // a[lo..i] <= pivot
    for (int j = lo; j < hi; ++j)
        if (++comparisons; a[j] <= pivot) swap(a[++i], a[j]);
    swap(a[i + 1], a[hi]);                         // pivot to its final place
    return i + 1;
}
void quickSort(vector<int>& a, int lo, int hi, int depth) {
    if (lo >= hi) return;
    maxDepth = max(maxDepth, depth);
    int p = partition(a, lo, hi);
    if (show) {
        printf("%*s[%d..%d] pivot %d:", 2 * depth - 2, "", lo, hi, a[p]);
        for (int t = lo; t <= hi; ++t) printf(t == p ? " [%d]" : " %d", a[t]);
        printf("\n");
    }
    quickSort(a, lo, p - 1, depth + 1);
    quickSort(a, p + 1, hi, depth + 1);
}
int main() {
    vector<int> a{4, 7, 2, 6, 1, 8, 3, 5};
    quickSort(a, 0, 7, 1);
    printf("sorted:"); for (int x : a) printf(" %d", x);
    printf("\ncomparisons = %lld, max depth = %d\n", comparisons, maxDepth);
    show = 0;
    for (int n : {8, 16, 32}) {
        vector<int> b(n); for (int v = 0; v < n; ++v) b[v] = v + 1;  // sorted: the worst case
        comparisons = maxDepth = 0;
        quickSort(b, 0, n - 1, 1);
        printf("sorted input n = %d: comparisons = %lld, max depth = %d\n", n, comparisons, maxDepth);
    }
}

[0..7] pivot 5: 4 2 1 3 [5] 8 6 7
  [0..3] pivot 3: 2 1 [3] 4
    [0..1] pivot 1: [1] 2
  [5..7] pivot 7: 6 [7] 8
sorted: 1 2 3 4 5 6 7 8
comparisons = 13, max depth = 3
sorted input n = 8: comparisons = 28, max depth = 7
sorted input n = 16: comparisons = 120, max depth = 15
sorted input n = 32: comparisons = 496, max depth = 31

comparisons = max_depth = 0
show = True

def partition(a, lo, hi):              # Lomuto: pivot = last element
    global comparisons
    pivot, i = a[hi], lo - 1           # a[lo..i] <= pivot
    for j in range(lo, hi):
        comparisons += 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]  # pivot to its final place
    return i + 1

def quick_sort(a, lo, hi, depth):
    global max_depth
    if lo >= hi:
        return
    max_depth = max(max_depth, depth)
    p = partition(a, lo, hi)
    if show:
        part = ' '.join(f'[{a[t]}]' if t == p else str(a[t]) for t in range(lo, hi + 1))
        print(f"{'  ' * (depth - 1)}[{lo}..{hi}] pivot {a[p]}: {part}")
    quick_sort(a, lo, p - 1, depth + 1)
    quick_sort(a, p + 1, hi, depth + 1)

a = [4, 7, 2, 6, 1, 8, 3, 5]
quick_sort(a, 0, len(a) - 1, 1)
print("sorted:", *a)
print(f"comparisons = {comparisons}, max depth = {max_depth}")
show = False
for n in (8, 16, 32):
    comparisons = max_depth = 0
    quick_sort(list(range(1, n + 1)), 0, n - 1, 1)   # already sorted: the worst case
    print(f"sorted input n = {n}: comparisons = {comparisons}, max depth = {max_depth}")

[0..7] pivot 5: 4 2 1 3 [5] 8 6 7
  [0..3] pivot 3: 2 1 [3] 4
    [0..1] pivot 1: [1] 2
  [5..7] pivot 7: 6 [7] 8
sorted: 1 2 3 4 5 6 7 8
comparisons = 13, max depth = 3
sorted input n = 8: comparisons = 28, max depth = 7
sorted input n = 16: comparisons = 120, max depth = 15
sorted input n = 32: comparisons = 496, max depth = 31

৩ · Hoare partition — দুই প্রান্ত থেকে মুখোমুখি

Hoare-এর নিজের ১৯৬১ সালের পদ্ধতিটি আলাদা। দুটি pointer দুই প্রান্ত থেকে মাঝের দিকে এগোয়: i বাঁ থেকে খোঁজে এমন উপাদান যা pivot-এর চেয়ে বড় বা সমান (অর্থাৎ ভুল দিকে আছে), j ডান থেকে খোঁজে এমন উপাদান যা pivot-এর চেয়ে ছোট বা সমান। দুজনেই থামলে তাদের swap — একসাথে দুটি ভুল-জায়গার উপাদান ঠিক দিকে চলে যায়। Pointer দুটি একে অপরকে পার হলে কাজ শেষ। ট্রেনের দুই প্রান্ত থেকে দুজন টিকিট-চেকারের কথা ভাবুন: প্রত্যেকে নিজের দিক থেকে ভুল বগিতে বসা একজন যাত্রী খুঁজে পেলেই দুজনে যাত্রী বদলে নেন। এই রূপটিকে বলে Hoare partition.

Pseudocode — Hoare partition (0-based, pivot = first element)

partition(A, lo, hi):
    pivot = A[lo]
    i = lo - 1;  j = hi + 1
    loop:
        repeat j = j - 1 until A[j] <= pivot
        repeat i = i + 1 until A[i] >= pivot
        if i < j: swap A[i], A[j]
        else: return j               // A[lo..j] <= pivot <= A[j+1..hi]

quicksort(A, lo, hi):                // with Hoare: recurse on lo..j and j+1..hi
    if lo < hi:
        j = partition(A, lo, hi)
        quicksort(A, lo, j);  quicksort(A, j + 1, hi)

একই অ্যারে [4, 7, 2, 6, 1, 8, 3, 5], কিন্তু এবার pivot প্রথম উপাদান 4:

৪ · বিশ্লেষণ — সেরা, গড় আর সবচেয়ে খারাপ

n উপাদানের অংশে partition নেয় Θ(n). Pivot যদি ছোট দিকে q টি আর বড় দিকে n − q − 1 টি উপাদান রাখে, তাহলে recurrence:

সেরা ক্ষেত্র (best case): প্রতিবার pivot ঠিক median, q ≈ n/2. তখন T(n) = 2T(n/2) + Θ(n) — merge sort-এর হুবহু recurrence, master theorem-এর (পর্ব ০৯) দ্বিতীয় ক্ষেত্র: Θ(n log n). Recursion tree-র প্রতিটি স্তরে মোট কাজ প্রায় n, স্তর log₂ n টি।

সবচেয়ে খারাপ ক্ষেত্র (worst case): প্রতিবার pivot সবচেয়ে ছোট বা সবচেয়ে বড়, q = 0. তখন T(n) = T(n − 1) + Θ(n), যার সমাধান (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 = Θ(n²). কখন এমন হয়? সবচেয়ে সাধারণ উদাহরণ: আগে থেকেই সাজানো (বা উল্টো সাজানো) অ্যারে, আর pivot প্রথম বা শেষ উপাদান। বাস্তবে এমন ইনপুট মোটেই বিরল নয় — বাজারের দামের তালিকা যা গতকালই সাজানো হয়েছিল, তাতে দুটি নতুন দাম যোগ হয়েছে। নিচে [1, 2, 3, 4, 5, 6]-এ শেষ উপাদান pivot ধরে প্রতিটি রিকার্সিভ কল দেখুন:

মাঝামাঝি ভাগও যথেষ্ট ভালো। প্রতিবার ভাগ যদি 9 : 1 অনুপাতেও হয় — খুবই একপেশে — তবু recursion tree-র গভীরতা log_10/9 n (n = 10⁶-এ প্রায় ১৩১), আর প্রতিটি স্তরে কাজ ≤ n. ফল এখনো Θ(n log n), শুধু ধ্রুবকটি বড়। অর্থাৎ quick sort-এর জন্য নিখুঁত median লাগে না; লাগে শুধু এটুকু যে pivot বারবার একেবারে প্রান্তের হবে না।

গড় ক্ষেত্র (average case): সব ক্রম সমান সম্ভাব্য ধরলে (n! টি ক্রমের প্রতিটি), pivot-এর rank 1 থেকে n-এর যেকোনোটি সমান সম্ভাবনায় হয়। তখন প্রত্যাশিত তুলনার সংখ্যা প্রায় 2n ln n ≈ 1.39 n log₂ n — Θ(n log n), best case-এর চেয়ে মাত্র ৩৯% বেশি। ভালো আর খারাপ ভাগ মিশে থাকে, আর একটি খারাপ ভাগের পরে একটি ভালো ভাগ এলেই ক্ষতি পুষিয়ে যায়।

৫ · Pivot বাছাই আর randomized quicksort

Worst case নির্ভর করে pivot বাছাইয়ের নিয়মের ওপর। প্রচলিত নিয়মগুলো:

লক্ষ করুন: যেকোনো নির্দিষ্ট (deterministic) নিয়মের জন্য এমন একটি ইনপুট বানানো যায় যা প্রতিবার সবচেয়ে খারাপ pivot দেয় — কারণ শত্রু আগে থেকেই জানে আপনি কোন ঘর বাছবেন। এমন ইচ্ছাকৃত ইনপুটকে বলে adversarial input. সমাধান হলো শত্রুর কাছ থেকে সিদ্ধান্তটি লুকিয়ে ফেলা: pivot বাছুন এলোমেলোভাবে। এটিই randomized quicksort — একটি randomized algorithm.

Pseudocode — randomized partition (0-based)

randomized_partition(A, lo, hi):
    r = random integer in [lo, hi]   // every index equally likely
    swap A[r], A[hi]                 // the random element becomes the pivot
    return partition(A, lo, hi)      // ordinary Lomuto from here on

ফল (প্রমাণ পর্ব ৬১-এ): যেকোনো n উপাদানের ইনপুটে — সাজানো, উল্টো, বা শত্রুর বানানো — randomized quicksort-এর expected running time O(n log n), আর প্রত্যাশিত তুলনা প্রায় 2n ln n. এখানে “প্রত্যাশা” নেওয়া হচ্ছে অ্যালগরিদমের নিজের coin toss-এর ওপর, ইনপুটের ওপর নয়। তাই এটি “ইনপুট এলোমেলো হলে গড়ে ভালো” বলার চেয়ে অনেক শক্ত দাবি: কোনো খারাপ ইনপুটই আর নেই — আছে শুধু খারাপ ভাগ্য, আর তার সম্ভাবনা n বাড়ার সাথে দ্রুত শূন্যের দিকে যায়।

মূল যুক্তির আভাস. সাজানো ক্রমে উপাদানগুলোকে z₁ < z₂ < … < z_n বলি। Quick sort-এ দুটি উপাদানের তুলনা হয় শুধু তখনই, যখন তাদের একটি pivot — আর একবার তুলনা হওয়ার পর তারা আলাদা হয়ে যায় বা pivot সরে যায়, তাই কোনো জোড়া দুবার তুলনা হয় না। z_i আর z_j-এর তুলনা হবে ঠিক তখনই, যখন z_i, z_i+1, …, z_j — এই j − i + 1 টি উপাদানের মধ্যে প্রথম যে pivot হয়, সে z_i বা z_j. মাঝের কেউ আগে pivot হলে দুজন দুই দিকে চলে যায়, আর কখনো দেখা হয় না। এলোমেলো pivot-এ এই সম্ভাবনা 2/(j − i + 1). সব জোড়ার যোগফল প্রায় 2n · (1 + 1/2 + 1/3 + … + 1/n) = 2n H_n ≈ 2n ln n — পর্ব ০৬-এর harmonic series এখানে কাজে লাগল।

৬ · ডুপ্লিকেট আর 3-way partition — ডাচ পতাকা ফিরে এলো

ধরুন একটি বোর্ড পরীক্ষার ১০ লক্ষ খাতা GPA অনুযায়ী সাজাতে হবে। GPA-র আলাদা মান মাত্র কয়েক ডজন — অর্থাৎ বিপুল ডুপ্লিকেট। Lomuto-তে pivot-এর সমান সব উপাদান বাঁ দিকে যায়; সব-সমান অংশে প্রতিটি partition মাত্র একটি উপাদান (pivot) কমায় — আবার Θ(n²). Hoare এটি সামলায়, কিন্তু সমান উপাদানগুলো নিয়ে বারবার রিকার্শন চালিয়ে যায়।

ভালো সমাধান: অংশটিকে তিন ভাগে ভাগ করা — pivot-এর চেয়ে ছোট, সমান, বড়। সমান অংশটি তখনই চূড়ান্ত; রিকার্শন হয় শুধু ছোট আর বড় অংশে। এটিই 3-way partition, আর এটি পর্ব ১৬-এর Dutch national flag সমস্যার হুবহু রূপ: তিনটি pointer lt, i, gt. A[lo..lt−1] < pivot, A[lt..i−1] = pivot, A[gt+1..hi] > pivot, আর A[i..gt] এখনো দেখা হয়নি।

Pseudocode — 3-way partition (0-based, Dijkstra's Dutch flag)

pivot = A[lo];  lt = lo;  i = lo;  gt = hi
while i <= gt:
    if A[i] < pivot:   swap A[lt], A[i];  lt++;  i++
    elif A[i] > pivot: swap A[i], A[gt];  gt--          // do NOT advance i
    else:              i++
// now recurse on A[lo..lt-1] and A[gt+1..hi] only

যদি অ্যারেতে মাত্র k টি আলাদা মান থাকে, 3-way quick sort প্রত্যাশিত O(n log k) সময় নেয় — সব-সমান অ্যারেতে মাত্র এক পাস, Θ(n). ১৯৯৩ সালে Jon Bentley আর Douglas McIlroy “Engineering a Sort Function” প্রবন্ধে C লাইব্রেরির qsort-এর জন্য একটি দ্রুত 3-way রূপ দেন, যা পরে বহু লাইব্রেরিতে গৃহীত হয়।

৭ · Stack-এর গভীরতা, ছোট ভাগে রিকার্শন আর stability

অংশ ৪-এর stepper-এ দেখেছেন, একপেশে ভাগে recursion depth হয় n. প্রতিটি স্তর call stack-এ একটি frame — দশ লক্ষ উপাদানে নিশ্চিত stack overflow. এর একটি সুন্দর প্রতিকার আছে, যা সময় না বদলেও জায়গা নিশ্চিতভাবে কমায়:

// quick sort with O(log n) stack: recurse on the smaller side, loop on the larger
void quickSort(vector<int>& a, int lo, int hi) {
    while (lo < hi) {
        int p = partition(a, lo, hi);          // Lomuto from section 2
        if (p - lo < hi - p) {                 // left side is smaller
            quickSort(a, lo, p - 1);
            lo = p + 1;                        // continue with the right side
        } else {
            quickSort(a, p + 1, hi);
            hi = p - 1;                        // continue with the left side
        }
    }
}

এটি আসলে হাতে করা tail-call elimination. সরল কোডের দ্বিতীয় রিকার্সিভ কলটি ফাংশনের একেবারে শেষ কাজ — একটি tail call (পর্ব ০৭). ভালো C++ compiler অপটিমাইজেশন চালু থাকলে নিজেই সেটিকে লুপে বদলে দিতে পারে, কিন্তু তাতে শুধু দ্বিতীয় কলটি বাদ যায় — বড় ভাগটি প্রথম কলে পড়লে গভীরতা তবু n হতে পারে। কোন ভাগ ছোট তা দেখে সিদ্ধান্ত নেওয়াটাই গ্যারান্টি দেয়। Python কখনো tail call অপটিমাইজ করে না, তাই সেখানে এই লুপ-রূপ বা নিজের একটি explicit stack অপরিহার্য। অংশ ৪-এর সাজানো ইনপুটে মজার ঘটনা ঘটে: ছোট ভাগটি সবসময় খালি, তার রিকার্সিভ কল সাথে সাথে ফিরে আসে, তাই stack-এ কখনো দুটির বেশি frame জমে না — অথচ সময় এখনো Θ(n²).

In-place, কিন্তু stable নয়

Quick sort in-place: partition চলে O(1) বাড়তি জায়গায়, আর পুরো অ্যালগরিদমে বাড়তি শুধু রিকার্শনের stack — ওপরের কৌশলে O(log n). Merge sort-এর Θ(n) বাড়তি অ্যারের তুলনায় এটি বড় সুবিধা।

কিন্তু quick sort stable নয়: সমান key-এর উপাদানগুলোর আগের ক্রম রক্ষা হয় না, কারণ swap উপাদানদের দূরে লাফিয়ে নিয়ে যায়। উদাহরণ: তিনজন পরীক্ষার্থী, নম্বর অনুযায়ী সাজাতে হবে — [(3, Anik), (3, Bithi), (1, Rafi)], যেখানে Anik আগে, Bithi পরে। Lomuto-তে pivot (1, Rafi); কেউ ≤ 1 নয়, তাই শেষ swap A[0] ⇄ A[2]: [(1, Rafi), (3, Bithi), (3, Anik)]. ডান অংশে আর কিছু বদলায় না। Bithi এখন Anik-এর আগে — সমান নম্বরের দুজনের ক্রম উল্টে গেছে। Stability দরকার হলে merge sort, C++-এর std::stable_sort, বা Python-এর sorted (Timsort) ব্যবহার করুন (পর্ব ২৫).

৮ · Introsort — quick + heap + insertion, std::sort-এর ভেতরে

Randomized quicksort-এর worst case-এর সম্ভাবনা নগণ্য, কিন্তু শূন্য নয়; আর লাইব্রেরি লেখকেরা গ্যারান্টি চান। ১৯৯৭ সালে David Musser একটি মিশ্র পদ্ধতি দেন, নাম introsort (introspective sort — যে নিজের অবস্থা নিজে পর্যবেক্ষণ করে):

1. শুরুতে quick sort (সাধারণত median-of-three pivot দিয়ে) — কারণ গড়ে এটিই সবচেয়ে দ্রুত।
2. রিকার্শন বেশি গভীর হলে heapsort: গভীরতা একটি সীমা (সাধারণত 2⌊log₂ n⌋) পার হলে বোঝা যায় ভাগগুলো খারাপ হচ্ছে; তখন সেই অংশটি heapsort-এ (পর্ব ২৩) সাজানো হয়, যার worst case O(n log n).
3. ছোট টুকরোয় insertion sort: ১৬-র মতো ছোট অংশে রিকার্শনের খরচ কাজের চেয়ে বেশি; সেখানে insertion sort (পর্ব ২০) দ্রুততর।

ফল: গড়ে quick sort-এর গতি, worst case-এ O(n log n), আর বাড়তি জায়গা O(log n). GCC-র libstdc++ আর অন্যান্য প্রধান C++ লাইব্রেরির std::sort introsort বা তার কাছাকাছি কোনো রূপ ব্যবহার করে। C++11 থেকে standard নিজেই std::sort-এর জন্য worst case O(n log n) তুলনা দাবি করে — C++98 শুধু গড় দাবি করত, যা সরল quick sort-এও মিটত। অন্য ভাষার পছন্দ আলাদা: Java primitive অ্যারের জন্য Vladimir Yaroslavskiy-র dual-pivot quicksort (দুটি pivot, তিন ভাগ) ব্যবহার করে, আর object-এর জন্য stable Timsort; Python-এর list.sort শুধুই Timsort. Orson Peters-এর pdqsort (pattern-defeating quicksort) — introsort-এর আধুনিক উত্তরসূরি — Rust আর Go-র unstable sort-এর ভিত্তি হয়েছে।

৯ · Quickselect আর median of medians — k-তম ছোট, পুরো সর্ট ছাড়াই

বোর্ড পরীক্ষার ফলের পর একজন সাংবাদিক জানতে চান median নম্বর কত — অর্থাৎ ঠিক মাঝের পরীক্ষার্থীর নম্বর। পুরো তালিকা সাজিয়ে মাঝেরটি নিলে O(n log n). কিন্তু আমাদের তো পুরো ক্রম দরকার নেই, দরকার শুধু একটি উপাদান। এই প্রশ্নের সাধারণ রূপ: k-তম ছোট উপাদান খোঁজা, যাকে বলে k-তম order statistic; k = 1 হলে minimum, k = n হলে maximum, মাঝামাঝি k হলে median.

Hoare-এর Find (১৯৬১), আজ যার নাম quickselect, একটি সরল পর্যবেক্ষণের ওপর দাঁড়ানো: partition-এর পর pivot index p-তে বসে, অর্থাৎ সে নিজেই (0-based) p-তম ছোট। এখন তিনটি সম্ভাবনা — k = p হলে উত্তর পেয়ে গেছি; k < p হলে উত্তর বাঁ অংশে, ডান অংশ পুরোটা ফেলে দিন; k > p হলে উত্তর ডানে, বাঁ অংশ ফেলে দিন। Quick sort দুই দিকেই রিকার্শন করে, quickselect করে মাত্র এক দিকে — binary search-এর (পর্ব ১৮) মতো।

কেন প্রত্যাশিত O(n). প্রতিবার pivot যদি অংশটিকে মোটামুটি অর্ধেক করে, কাজ হয় n + n/2 + n/4 + … ≤ 2n — পর্ব ০৬-এর geometric series. এলোমেলো pivot-এ প্রতিটি রাউন্ড অর্ধেক না করলেও, গড়ে অংশ একটি ধ্রুবক অনুপাতে ছোট হয়; ফল প্রত্যাশিত Θ(n) (median-এর জন্য প্রায় 3.4n তুলনা). Worst case অবশ্য quick sort-এর মতোই Θ(n²): সাজানো অ্যারেতে শেষ উপাদান pivot হলে প্রতিবার মাত্র একটি উপাদান বাদ যায়। নিচের কোড দুটি pivot নিয়মে দুই ধরনের ইনপুটে তুলনা গোনে:

#include <cstdio>
#include <vector>
#include <utility>
#include <initializer_list>
using namespace std;
int partition(vector<int>& a, int lo, int hi, long& cnt) {   // Lomuto, pivot = a[hi]
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; ++j)
        if (++cnt; a[j] <= pivot) swap(a[++i], a[j]);
    swap(a[i + 1], a[hi]);
    return i + 1;
}
int quickselect(vector<int> a, int k, bool mo3, long& cnt) {  // k-th smallest, 0-based
    int lo = 0, hi = (int)a.size() - 1;
    while (lo < hi) {
        if (mo3) {                          // median of a[lo], a[mid], a[hi] -> a[hi]
            int mid = (lo + hi) / 2;
            if (a[mid] < a[lo]) swap(a[mid], a[lo]);
            if (a[hi] < a[lo]) swap(a[hi], a[lo]);
            if (a[mid] < a[hi]) swap(a[mid], a[hi]);
        }
        int p = partition(a, lo, hi, cnt);
        if (k == p) return a[p];
        if (k < p) hi = p - 1; else lo = p + 1;   // keep only the side holding k
    }
    return a[lo];
}
int main() {
    const int n = 101;
    vector<int> mixed(n), sorted(n);
    for (int i = 0; i < n; ++i) mixed[i] = (i * 37) % n, sorted[i] = i;  // mixed: a fixed shuffle
    for (auto [name, data] : {pair{"mixed", mixed}, pair{"sorted", sorted}})
        for (bool mo3 : {false, true}) {
            long cnt = 0;
            int med = quickselect(data, n / 2, mo3, cnt);
            printf("%-6s pivot=%-11s median = %d, comparisons = %ld\n",
                   name, mo3 ? "median-of-3" : "last", med, cnt);
        }
}

mixed  pivot=last        median = 50, comparisons = 277
mixed  pivot=median-of-3 median = 50, comparisons = 267
sorted pivot=last        median = 50, comparisons = 3825
sorted pivot=median-of-3 median = 50, comparisons = 100

def partition(a, lo, hi, cnt):         # Lomuto, pivot = a[hi]
    pivot, i = a[hi], lo - 1
    for j in range(lo, hi):
        cnt[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 quickselect(a, k, mo3, cnt):       # k-th smallest, 0-based
    lo, hi = 0, len(a) - 1
    while lo < hi:
        if mo3:                        # median of a[lo], a[mid], a[hi] -> a[hi]
            mid = (lo + hi) // 2
            if a[mid] < a[lo]: a[mid], a[lo] = a[lo], a[mid]
            if a[hi] < a[lo]: a[hi], a[lo] = a[lo], a[hi]
            if a[mid] < a[hi]: a[mid], a[hi] = a[hi], a[mid]
        p = partition(a, lo, hi, cnt)
        if k == p: return a[p]
        if k < p: hi = p - 1           # answer is on the left: drop the right
        else: lo = p + 1               # answer is on the right: drop the left
    return a[lo]

n = 101
mixed = [(i * 37) % n for i in range(n)]   # a fixed shuffle of 0..100
for name, data in (("mixed", mixed), ("sorted", list(range(n)))):
    for mo3 in (False, True):
        cnt = [0]
        med = quickselect(data[:], n // 2, mo3, cnt)
        rule = "median-of-3" if mo3 else "last"
        print(f"{name:6} pivot={rule:11} median = {med}, comparisons = {cnt[0]}")

mixed  pivot=last        median = 50, comparisons = 277
mixed  pivot=median-of-3 median = 50, comparisons = 267
sorted pivot=last        median = 50, comparisons = 3825
sorted pivot=median-of-3 median = 50, comparisons = 100

লাইব্রেরিতে: C++-এর std::nth_element(v.begin(), v.begin() + k, v.end()) গড়ে linear সময়ে k-তম উপাদানকে তার সাজানো ঘরে বসায়, বাঁয়ে ছোট আর ডানে বড় রেখে (libstdc++ ভেতরে introselect — quickselect আর একটি worst-case-নিরাপদ পদ্ধতির মিশ্রণ — ব্যবহার করে). Python-এর standard library-তে সরাসরি quickselect নেই: statistics.median ভেতরে সর্ট করে (O(n log n)), আর ছোট k-এর জন্য heapq.nsmallest(k, a) লাগে O(n log k). NumPy-র numpy.partition introselect ব্যবহার করে।

Median of medians — worst case-এও O(n)

Quickselect-কে worst case-এ linear করা যায় কি? ১৯৭৩ সালে পাঁচজন — Manuel Blum, Robert Floyd, Vaughan Pratt, Ronald Rivest আর Robert Tarjan — “Time Bounds for Selection” প্রবন্ধে দেখান, হ্যাঁ। তাঁদের নামের আদ্যক্ষর থেকে একে BFPRT অ্যালগরিদমও বলে, আর সাধারণ নাম median of medians. কৌশল হলো pivot এমনভাবে বাছা, যাতে সে নিশ্চিতভাবে মাঝামাঝি হয়:

1. n উপাদানকে ৫টি করে দলে ভাগ করুন (⌈n/5⌉ টি দল).
2. প্রতিটি দলের median বের করুন — ৫টি উপাদান, তাই প্রতিটি O(1), মোট O(n).
3. এই ⌈n/5⌉ টি median-এর median x বের করুন — রিকার্সিভভাবে এই একই অ্যালগরিদম দিয়ে।
4. x-কে pivot ধরে partition, তারপর quickselect-এর মতো শুধু এক দিকে রিকার্শন।

ছোট একটি উদাহরণ, ১৫টি উপাদান তিনটি দলে:

Median-গুলো {12, 14, 11}, এদের median x = 12. x-এর চেয়ে ছোট বা সমান উপাদান ৮টি, বড় ৭টি — প্রায় নিখুঁত ভাগ।

কেন ভাগ নিশ্চিতভাবে ভালো. দলগুলোর অর্ধেকের median ≥ x (x নিজে median-গুলোর median বলে). এমন প্রতিটি দলে অন্তত ৩টি উপাদান (median আর তার চেয়ে বড় দুটি) ≥ x. দলের সংখ্যা n/5, তার অর্ধেক n/10, প্রতিটিতে ৩ — তাই অন্তত প্রায় 3n/10 টি উপাদান x-এর চেয়ে বড় বা সমান। একইভাবে অন্তত প্রায় 3n/10 টি ছোট বা সমান। অতএব যেদিকেই রিকার্শন হোক, অংশটির মাপ সর্বোচ্চ প্রায় 7n/10 (নিখুঁত হিসাবে সীমানার দলগুলোর জন্য 7n/10 + 6). সময়ের recurrence:

প্রমাণ (substitution, পর্ব ০৮): ধরি O(n) অংশটি ≤ an, আর অনুমান করি T(m) ≤ cm সব ছোট m-এর জন্য। তাহলে T(n) ≤ c(n/5) + c(7n/10) + an = (9/10)cn + an. এটি ≤ cn হবে যদি an ≤ cn/10, অর্থাৎ c ≥ 10a. তাই T(n) = O(n). মূল কারণ: দুই রিকার্সিভ অংশের মোট মাপ n/5 + 7n/10 = 9n/10 < n — প্রতিটি স্তরে মোট কাজ জ্যামিতিক হারে কমে। ৩-এর দলে ভাঙলে এই অনুপাত হয় n/3 + 2n/3 = n, আর সরল সংস্করণে ফল দাঁড়ায় Θ(n log n); ৭-এর দলও কাজ করে। Recursion tree-র চোখে দেখলে: মূলে কাজ an, পরের স্তরে (9/10)an, তারপর (9/10)²an… — যোগফল ≤ 10an.

তত্ত্বে চমৎকার, কিন্তু ধ্রুবক বড় — প্রতিটি স্তরে দল বানানো আর দুটি রিকার্শন। তাই বাস্তবে randomized quickselect-ই বেশি দ্রুত; median of medians ব্যবহৃত হয় introselect-এর মতো মিশ্র পদ্ধতিতে “শেষ ভরসা” হিসেবে, যখন quickselect খারাপ চলছে বলে ধরা পড়ে। এটি দিয়ে quick sort-এর pivot বাছলে quick sort-ও তত্ত্বে worst case Θ(n log n) হয়, কিন্তু বাস্তবে introsort-এর চেয়ে ধীর।

১০ · AI-এর যুগে quick sort — চেনা কোড, অচেনা ভুল

Quick sort এত পরিচিত যে AI এক সেকেন্ডে লিখে দেয়। কিন্তু চেনা কোডেই ভুল সবচেয়ে বিপজ্জনক, কারণ আমরা সেটি খুঁটিয়ে দেখি না। Partition-এর সীমায় একটি off-by-one, Hoare-এ ভুল pivot, বা “quick sort সবসময় O(n log n)” — এমন দাবি AI-এর উত্তরে প্রায়ই পাওয়া যায়। এলোমেলো ছোট ইনপুটে সব ঠিক দেখায়; সাজানো, সব-সমান বা বড় ইনপুটে ধরা পড়ে।

Quick sort-এর কোডে AI সাধারণত যেসব ভুল করে

Quick sort-এর কোড যাচাইয়ের চেকলিস্ট

• ছোট একটি অ্যারেতে খাতায় প্রতিটি swap-এর পর অ্যারে লিখে কোডের ছাপা অবস্থার সাথে মিলিয়েছি (dry run)
• Edge case চালিয়েছি: খালি, এক উপাদান, দুই উপাদান, সব সমান, সাজানো, উল্টো সাজানো
• হাজারটি এলোমেলো ছোট অ্যারেতে লাইব্রেরির sort-এর সাথে ফল মিলিয়ে stress testing করেছি
• সাজানো 10⁵ উপাদানে সময় আর রিকার্শনের গভীরতা মেপেছি — crash বা কয়েক সেকেন্ড লাগলে pivot আর ছোট-ভাগ রিকার্শন ঠিক করেছি
• Partition-এর loop invariant নিজের ভাষায় লিখতে পারি, আর Hoare-এ কেন pivot A[hi] নয় তা ব্যাখ্যা করতে পারি
• Complexity-র প্রতিটি দাবিতে বলেছি কোনটি worst, কোনটি average, আর কোনটি expected (random pivot)