Counting, radix আর bucket sort — আর তুলনা-সর্টের নিম্নসীমা

১ · তুলনা করে সাজানো — আর পরীক্ষার খাতার এক অন্য উপায়

পর্ব ২০ থেকে ২৩ পর্যন্ত আপনি যত সর্ট দেখেছেন — insertion, merge, quick, heap — সবার মধ্যে একটি মিল আছে। এরা উপাদান সম্পর্কে একটিই প্রশ্ন করে: “a কি b-এর চেয়ে ছোট বা সমান?” উত্তর হ্যাঁ বা না। এর বাইরে কিছু জানে না, জানতেও চায় না। এই ধরনের অ্যালগরিদমকে বলে comparison sort (তুলনা-ভিত্তিক সর্ট)। এদের সুবিধা বিশাল: যে জিনিসেরই তুলনা করা যায় — সংখ্যা, নাম, তারিখ, এমনকি আপনার নিজের বানানো struct — সবই একই কোডে সাজানো যায়, শুধু একটি comparator দিলেই।

কিন্তু এই সর্বজনীনতার একটি দাম আছে। পর্ব ২১-এ merge sort Θ(n log n) নিয়েছিল, পর্ব ২৩-এ heapsort-ও তাই। প্রশ্ন জাগে: আরও চালাক কোনো তুলনা-সর্ট কি O(n)-এ পারবে? এই পর্বের প্রথম অর্ধেক প্রমাণ করবে — না, কখনোই না। তারপর দ্বিতীয় অর্ধেক দেখাবে, তুলনা ছেড়ে দিলে কীভাবে সত্যিই রৈখিক সময়ে সাজানো যায়।

দ্বিতীয় উপায়টি কাজ করেছে কারণ আমরা key সম্পর্কে একটি বাড়তি তথ্য জানতাম: রোল নম্বর ১ থেকে ৬০-এর মধ্যে একটি পূর্ণসংখ্যা। নাম দিয়ে সাজাতে হলে এভাবে ঘর আঁকা যেত না — অন্তত এত সহজে নয়। এই পর্বের প্রতিটি দ্রুত অ্যালগরিদম এমনই কোনো বাড়তি তথ্যের ওপর দাঁড়িয়ে: key-এর পরিসর ছোট (counting sort), key নির্দিষ্ট সংখ্যক অঙ্কে লেখা (radix sort), অথবা key একটি পরিসরে সমভাবে ছড়ানো (bucket sort).

২ · Decision tree — কেন তুলনা-সর্ট n log n-এর নিচে নামতে পারে না

একটি অ্যালগরিদমের পক্ষে “এর চেয়ে দ্রুত সম্ভব নয়” প্রমাণ করা সাধারণত কঠিন, কারণ বিশ্বের সব সম্ভাব্য অ্যালগরিদমের কথা একসাথে বলতে হয় — যেগুলো এখনো কেউ আবিষ্কারই করেনি সেগুলোরও। তুলনা-সর্টের জন্য একটি সুন্দর কৌশল আছে: যেকোনো তুলনা-সর্টকে একটি decision tree হিসেবে আঁকা যায়।

ধরুন n টি আলাদা উপাদান a₁, a₂, …, aₙ সাজাতে হবে। অ্যালগরিদম চলার সময় প্রথম যে তুলনাটি করে, সেটি tree-এর মূল (root). উত্তর “≤” হলে বাঁ দিকে, “>” হলে ডান দিকে যাই, আর সেখানে অ্যালগরিদমের পরের তুলনা। এভাবে চলতে চলতে অ্যালগরিদম যখন উত্তর জেনে যায়, তখন আমরা একটি পাতায় (leaf) পৌঁছাই — পাতায় লেখা থাকে চূড়ান্ত সাজানো ক্রমটি। অ্যালগরিদমের কোডে লুপ, ভ্যারিয়েবল, swap যা-ই থাকুক, n নির্দিষ্ট করে দিলে তুলনাগুলোর এই শাখা-প্রশাখাই তার পুরো আচরণ। নিচে n = 3-এর জন্য insertion sort-এর decision tree দেখুন, আর একটি নির্দিষ্ট ইনপুট কোন পথে যায় তা অনুসরণ করুন।

প্রমাণ — চার লাইনে

1. প্রতিটি ক্রমের জন্য অন্তত একটি পাতা। n টি আলাদা উপাদানের n! রকম বিন্যাস (permutation) সম্ভব। দুটি ভিন্ন বিন্যাস যদি একই পাতায় পৌঁছায়, তাহলে অ্যালগরিদম দুটির জন্য একই কাজ করবে — অথচ দুটির সঠিক উত্তর আলাদা, তাই অন্তত একটি ভুল হবে। সুতরাং সঠিক অ্যালগরিদমের tree-তে পাতা ≥ n!.
2. উচ্চতা h হলে পাতা ≤ 2ʰ. প্রতিটি তুলনায় শাখা সর্বোচ্চ দুটি, তাই প্রতি স্তরে পাতার সম্ভাব্য সংখ্যা সর্বোচ্চ দ্বিগুণ হয়।
3. তাই 2ʰ ≥ n!, অর্থাৎ h ≥ log₂ n!.
4. log₂ n! = Θ(n log n). n! = 1 · 2 · … · n-এর ওপরের n/2 টি গুণনীয়কের প্রতিটি ≥ n/2, তাই n! ≥ (n/2)^n/2, আর log₂ n! ≥ (n/2) log₂(n/2) = Ω(n log n). অন্যদিকে n! ≤ nⁿ, তাই log₂ n! ≤ n log₂ n. (পর্ব ০৬-এর Stirling-এর সূত্র আরও নিখুঁত: log₂ n! ≈ n log₂ n − 1.44 n.)

সংখ্যায় দেখলে সীমাটি কতটা কড়া বোঝা যায়। n = 4-এ 4! = 24 টি পাতা, log₂ 24 ≈ 4.58, তাই অন্তত ৫টি তুলনা। n = 10-এ 10! = 36,28,800 টি পাতা, log₂ 10! ≈ 21.8 — অন্তত ২২টি তুলনা। n = 10⁶-এ log₂ n! ≈ 1.85 × 10⁷, যেখানে n log₂ n ≈ 1.99 × 10⁷ — অর্থাৎ merge sort সীমার খুব কাছেই আছে।

গড়ের ক্ষেত্রেও একই সীমা। সব n! ইনপুট সমান সম্ভাবনার হলে গড় তুলনা = পাতাগুলোর গড় গভীরতা। n! টি পাতার একটি binary tree-তে গড় গভীরতাও অন্তত log₂ n! (সমান ভাগ হলেই গড় সবচেয়ে কম হয়, আর তখনও প্রতিটি পাতা প্রায় log₂ n! গভীরে)। তাই এলোমেলো pivot বা কোনো চালাকি দিয়েও গড়ে n log n-এর নিচে নামা যায় না।

তাহলে counting sort কীভাবে পারে?

প্রমাণের প্রথম লাইনেই একটি লুকানো অনুমান আছে: অ্যালগরিদম উপাদান সম্পর্কে শুধু তুলনার মাধ্যমে তথ্য পায়, আর প্রতিটি তুলনা মাত্র দুটি উত্তর দেয় (১ bit তথ্য)। Counting sort এই অনুমান ভাঙে। সে cnt[x]++ লিখে key x-কে সরাসরি অ্যারের index বানায় — এক ধাপে k টি সম্ভাব্য ঘরের যেকোনোটিতে লাফ দেয়, যা আসলে k-মুখী একটি সিদ্ধান্ত, দুই-মুখী নয়। পর্ব ০২-এর RAM model-এ অ্যারে-index O(1) সময়ের কাজ, তাই এই “k-মুখী লাফ” সস্তা। Decision tree-এর যুক্তি তাই এখানে খাটেই না; এর মানে এই নয় যে প্রমাণটি ভুল, বরং অ্যালগরিদমটি অন্য খেলার নিয়মে খেলছে।

৩ · Counting sort — গুনে গুনে জায়গা ঠিক করা

ধরুন n টি উপাদানের key 0 থেকে k-এর মধ্যে পূর্ণসংখ্যা — যেমন ১০ নম্বরের কুইজে প্রাপ্ত নম্বর, বয়স, অথবা ASCII অক্ষর। Counting sort তিন ধাপে কাজ করে:

1. গোনা: k + 1 ঘরের একটি cnt অ্যারে, যার cnt[v] = key v কতবার এসেছে। এটি পর্ব ১১-এর frequency array.
2. Prefix sum: cnt[v] += cnt[v-1] চালালে cnt[v] হয়ে যায় “v বা তার ছোট key কয়টি”। পর্ব ১৭-এর prefix sum এখানে একটি নতুন অর্থ পায়: key v-এর শেষ উপাদানটি আউটপুটে কোন ঘরে বসবে (cnt[v] − 1 নম্বর ঘরে, 0-based).
3. বসানো: ইনপুটের ডান থেকে বাঁয়ে হাঁটুন। প্রতিটি উপাদান x-এর জন্য cnt[key(x)] এক কমান, তারপর x-কে সেই ঘরে বসান।

শুধু সংখ্যা সাজালে ধাপ ২–৩ লাগে না: গোনার পর “0 লিখুন cnt[0] বার, 1 লিখুন cnt[1] বার…” করলেই হয়। কিন্তু বাস্তবে key-এর সাথে থাকে বাড়তি তথ্য — নম্বরের সাথে রোল, নাম, ঠিকানা। একে বলে satellite data. তখন পুরো রেকর্ড সরাতে হয়, আর ধাপ ২–৩-ই সেটি ঠিকঠাক করে। নিচে n = 6, k = 3-এর একটি ইনপুটে দেখুন; সমান key দুটিকে আলাদা চেনার জন্য 2a, 2b লেখা হয়েছে:

কেন ডান থেকে বাঁয়ে? প্রতিটি key-এর জন্য cnt[v] শুরুতে সেই key-এর অংশের শেষ ঘরের পরের ঘর দেখায়, আর প্রতিবার এক কমে বাঁয়ে সরে। ডান থেকে হাঁটলে যে উপাদান ইনপুটে শেষে, সে সবার আগে আসে আর বসে অংশের শেষ ঘরে; ফলে সমান key-দের আপেক্ষিক ক্রম অক্ষত থাকে। বাঁ থেকে হাঁটলেও সর্টেড ফল আসবে, কিন্তু সমান key-দের ক্রম উল্টে যাবে — সর্ট আর stable থাকবে না। (বিকল্প: prefix sum-কে এক ঘর ডানে সরিয়ে প্রতিটি key-এর প্রথম ঘর রাখুন, তারপর বাঁ থেকে হেঁটে প্রতিবার এক বাড়ান — সেটিও stable.) পরের অংশে দেখবেন, radix sort-এর পুরো শুদ্ধতা এই একটি বৈশিষ্ট্যের ওপর দাঁড়িয়ে।

বিশ্লেষণ: গোনা Θ(n), prefix sum Θ(k), বসানো Θ(n) — মোট সময় Θ(n + k). জায়গা: cnt-এর Θ(k) আর আউটপুটের Θ(n), তাই auxiliary space Θ(n + k); এটি in-place নয়। k = O(n) হলে পুরো সর্ট Θ(n) — n log n-এর সীমার নিচে। এবার (নম্বর, রোল) রেকর্ড সাজিয়ে stability নিজের চোখে দেখুন:

#include <cstdio>
#include <vector>
using namespace std;

struct Rec { int marks, roll; };

vector<Rec> countingSort(const vector<Rec>& a, int k) {
    vector<int> cnt(k + 1, 0);
    for (const Rec& r : a) cnt[r.marks]++;               // 1) count each key
    printf("count :"); for (int c : cnt) printf(" %d", c); printf("\n");
    for (int v = 1; v <= k; ++v) cnt[v] += cnt[v - 1];  // 2) prefix sums: keys <= v
    printf("prefix:"); for (int c : cnt) printf(" %d", c); printf("\n");
    vector<Rec> out(a.size());
    for (int i = (int)a.size() - 1; i >= 0; --i)        // 3) right to left = stable
        out[--cnt[a[i].marks]] = a[i];
    return out;
}

int main() {
    // (marks, roll) records, already in roll order; marks are 0..10
    vector<Rec> recs = {{7, 101}, {4, 102}, {9, 103}, {7, 104},
                        {4, 105}, {10, 106}, {9, 107}, {7, 108}};
    for (const Rec& r : countingSort(recs, 10))
        printf("marks %2d  roll %d\n", r.marks, r.roll);
}

count : 0 0 0 0 2 0 0 3 0 2 1
prefix: 0 0 0 0 2 2 2 5 5 7 8
marks  4  roll 102
marks  4  roll 105
marks  7  roll 101
marks  7  roll 104
marks  7  roll 108
marks  9  roll 103
marks  9  roll 107
marks 10  roll 106

# (marks, roll) records, already in roll order; marks are 0..10
recs = [(7, 101), (4, 102), (9, 103), (7, 104), (4, 105), (10, 106), (9, 107), (7, 108)]
K = 10

def counting_sort(a, key, k):
    cnt = [0] * (k + 1)
    for r in a:                    # 1) count each key
        cnt[key(r)] += 1
    print("count :", *cnt)
    for v in range(1, k + 1):      # 2) prefix sums: cnt[v] = number of keys <= v
        cnt[v] += cnt[v - 1]
    print("prefix:", *cnt)
    out = [None] * len(a)
    for r in reversed(a):          # 3) right to left keeps equal keys in order
        cnt[key(r)] -= 1
        out[cnt[key(r)]] = r
    return out

for marks, roll in counting_sort(recs, lambda r: r[0], K):
    print(f"marks {marks:2d}  roll {roll}")

count : 0 0 0 0 2 0 0 3 0 2 1
prefix: 0 0 0 0 2 2 2 5 5 7 8
marks  4  roll 102
marks  4  roll 105
marks  7  roll 101
marks  7  roll 104
marks  7  roll 108
marks  9  roll 103
marks  9  roll 107
marks 10  roll 106

k বড় হলে কী হয়?

Θ(n + k)-এর k-ই counting sort-এর দুর্বল জায়গা। ১০ লক্ষ মোবাইল রিচার্জের পরিমাণ (১০ থেকে ১০০০ টাকা) সাজাতে k ≈ 1000 — চমৎকার। কিন্তু একই ১০ লক্ষ লেনদেনের ১০ অঙ্কের ট্রানজ্যাকশন আইডি সাজাতে k ≈ 10¹⁰: cnt অ্যারেতেই লাগবে এক হাজার কোটি ঘর — 4 byte করে হলে ৪০ গিগাবাইট, যা সাধারণ কম্পিউটারে নেই। আর মেমরি থাকলেও prefix sum-এর Θ(k) লুপ n log n-এর চেয়ে বহুগুণ ধীর। মোটামুটি নিয়ম: k যদি n-এর কয়েক গুণের বেশি হয়, counting sort ছাড়ুন — radix sort নিন (অংশ ৪) অথবা সাধারণ std::sort.

৪ · Radix sort (LSD) — অঙ্ক ধরে ধরে, ডান থেকে বাঁয়ে

১০ লক্ষ শিক্ষার্থীর ছয় অঙ্কের রোল নম্বর সাজাতে চান। k = 10⁶ — counting sort চলে, কিন্তু টানাটানি করে। ৯ অঙ্কের সংখ্যা হলে আর চলে না। Radix sort-এর চালাকি: পুরো সংখ্যাকে একবারে key না বানিয়ে একটি একটি অঙ্ক ধরে সাজানো। প্রতিটি অঙ্কের পরিসর মাত্র 0..9, তাই প্রতিবার counting sort-এর cnt অ্যারেতে মাত্র ১০টি ঘর।

কিন্তু কোন অঙ্ক থেকে শুরু? মানুষ স্বাভাবিকভাবে বাঁয়ের (সবচেয়ে বড় মানের) অঙ্ক দিয়ে শুরু করতে চায়। LSD radix sort (Least Significant Digit) উল্টোটা করে: সবচেয়ে ডানের অঙ্ক দিয়ে শুরু, তারপর দশক, তারপর শতক… প্রতিটি pass-এ পুরো অ্যারেকে শুধু সেই অঙ্ক অনুযায়ী একটি stable counting sort দিয়ে সাজানো হয়। শুনে মনে হয় উল্টাপাল্টা — শেষ pass তো শুধু শতকের অঙ্ক দেখে, তাহলে বাকি অঙ্কের ক্রম ঠিক থাকে কীভাবে? নিচের তিন অঙ্কের রোল নম্বরগুলো দিয়ে দেখুন:

কেন ঠিক — stability-র ওপর induction

দাবি: i নম্বর pass-এর পর (ডান দিক থেকে i টি অঙ্ক দেখা হয়েছে) অ্যারেটি “শেষ i টি অঙ্ক দিয়ে গঠিত সংখ্যা” অনুযায়ী সাজানো।

• ভিত্তি (i = 1): প্রথম pass একক অঙ্ক দিয়ে সাজায় — দাবি সরাসরি সত্য।
• ধাপ (i − 1 থেকে i): দুটি সংখ্যা x আর y নিন। যদি তাদের i-তম অঙ্ক আলাদা হয়, তাহলে i-তম pass ছোট অঙ্কেরটিকে আগে রাখে — আর শেষ i অঙ্কের তুলনায় এই অঙ্কটিই নির্ধারক, তাই ঠিক। যদি i-তম অঙ্ক সমান হয়, তাহলে শেষ i অঙ্কের তুলনা নির্ভর করে শেষ i − 1 অঙ্কের ওপর; induction অনুযায়ী আগের pass-এর পর তারা সেই অনুযায়ী সাজানো ছিল, আর stable সর্ট সমান key-এর আগের ক্রম বদলায় না — তাই এখনো ঠিক।
• শেষে (i = d): সব d টি অঙ্ক দেখা হয়েছে, তাই অ্যারেটি পুরো সংখ্যা অনুযায়ী সাজানো। ∎

এটি পর্ব ০৩-এর mathematical induction-এর একটি পরিষ্কার প্রয়োগ, আর প্রমাণের ঠিক একটি জায়গায় stability লেগেছে — সেই জায়গাটিই পরীক্ষায় সবচেয়ে বেশি জিজ্ঞাসা করা হয়।

বিশ্লেষণ: d টি pass, প্রতিটি base b-এর একটি counting sort — Θ(n + b). মোট Θ(d(n + b)), জায়গা Θ(n + b). দশমিকে b = 10, তাই d অঙ্কের n টি সংখ্যায় Θ(d · n). d যদি ধ্রুবক হয় (যেমন সব রোল নম্বর ছয় অঙ্কের), radix sort রৈখিক। এবার আরেকটি ইনপুটে প্রতিটি pass-এর পরের অবস্থা চালিয়ে দেখুন — এখানে ডুপ্লিকেট আর দুই অঙ্কের সংখ্যাও আছে:

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> countingPass(const vector<int>& a, int exp) {  // stable sort on one digit
    int cnt[10] = {0};
    for (int x : a) cnt[x / exp % 10]++;
    for (int d = 1; d < 10; ++d) cnt[d] += cnt[d - 1];
    vector<int> out(a.size());
    for (int i = (int)a.size() - 1; i >= 0; --i)            // right to left = stable
        out[--cnt[a[i] / exp % 10]] = a[i];
    return out;
}

void show(const char* label, const vector<int>& a) {
    printf("%-14s", label);
    for (int x : a) printf(" %03d", x);
    printf("\n");
}

vector<int> radixSort(vector<int> a) {                     // LSD: least significant digit first
    show("input", a);
    const char* names[] = {"after ones", "after tens", "after hundreds", "after thousands"};
    int mx = a.empty() ? 0 : *max_element(a.begin(), a.end());
    for (int exp = 1, p = 0; mx / exp > 0; exp *= 10, ++p) {
        a = countingPass(a, exp);
        show(names[p], a);
    }
    return a;
}

int main() { radixSort({503, 87, 612, 45, 230, 87, 908, 16}); }

input          503 087 612 045 230 087 908 016
after ones     230 612 503 045 016 087 087 908
after tens     503 908 612 016 230 045 087 087
after hundreds 016 045 087 087 230 503 612 908

def counting_pass(a, exp):         # stable counting sort on one decimal digit
    cnt = [0] * 10
    for x in a:
        cnt[x // exp % 10] += 1
    for d in range(1, 10):
        cnt[d] += cnt[d - 1]
    out = [0] * len(a)
    for x in reversed(a):          # right to left = stable
        d = x // exp % 10
        cnt[d] -= 1
        out[cnt[d]] = x
    return out

def show(label, a):
    print(f"{label:<14}", *(f"{x:03d}" for x in a))

def radix_sort(a):                 # LSD: least significant digit first
    show("input", a)
    names = ["after ones", "after tens", "after hundreds", "after thousands"]
    mx = max(a, default=0)
    exp, p = 1, 0
    while mx // exp > 0:
        a = counting_pass(a, exp)
        show(names[p], a)
        exp, p = exp * 10, p + 1
    return a

radix_sort([503, 87, 612, 45, 230, 87, 908, 16])

input          503 087 612 045 230 087 908 016
after ones     230 612 503 045 016 087 087 908
after tens     503 908 612 016 230 045 087 087
after hundreds 016 045 087 087 230 503 612 908

৫ · Radix বেছে নেওয়া, MSD radix আর string সাজানো

Base 10 কেন নয় — byte ধরে ধরে

“অঙ্ক” মানে দশমিক অঙ্কই হতে হবে, এমন কোনো কথা নেই। কম্পিউটারে সংখ্যা থাকে bit-এ, তাই যেকোনো r টি bit-কে একটি “অঙ্ক” ধরা যায় — তখন radix (base) b = 2ʳ. w-bit key-তে pass লাগে d = ⌈w / r⌉, আর প্রতিটি অঙ্ক বের করা হয় shift আর mask দিয়ে: (x >> (r * pass)) & (b - 1) — ভাগ বা ভাগশেষের চেয়ে অনেক সস্তা।

সেরা r কত? মোট খরচ Θ((w / r)(n + 2ʳ)). r বাড়ালে pass কমে, কিন্তু প্রতি pass-এ 2ʳ খরচ বাড়ে। 2ʳ ≈ n হলে, অর্থাৎ r ≈ log₂ n, দুটি পদ সমান হয়, আর খরচ দাঁড়ায় Θ(w · n / log n). n = 10⁶ (log₂ n ≈ 20) আর w = 32 হলে প্রায় ২টি pass যথেষ্ট — কিন্তু বাস্তবে 2²⁰ ঘরের cnt cache-এ ধরে না, তাই অনেক লাইব্রেরি 8 বা 11 bit বেছে নেয়। তত্ত্বের হিসাব আর হার্ডওয়্যারের বাস্তবতা এখানে একসাথে সিদ্ধান্ত নেয়। তুলনায় merge sort-এ n = 10⁶-এ প্রায় 2 × 10⁷ তুলনা; base 256-এর radix sort-এ ৪টি pass, প্রতিটিতে n-এর কয়েক গুণ সরল কাজ।

MSD radix sort — বাঁ দিক থেকে, ফোনবুকের মতো

MSD radix sort (Most Significant Digit) মানুষের স্বাভাবিক পথ ধরে: প্রথমে সবচেয়ে বাঁয়ের অঙ্ক বা অক্ষর দিয়ে উপাদানগুলোকে b টি দলে ভাগ করে, তারপর প্রতিটি দলকে আলাদাভাবে পরের অঙ্ক দিয়ে রিকার্সিভভাবে সাজায়। ফোনবুক বা অভিধান বানানোর কথা ভাবুন: আগে সব নাম A, B, C… অনুযায়ী ভাগ, তারপর “B”-এর দলের ভেতরে দ্বিতীয় অক্ষর অনুযায়ী — “Ba…”, “Be…”, “Bi…”.

• Stability লাগে না দলগুলোর মধ্যে: দলগুলো একবার আলাদা হলে আর মেশে না, তাই পরের pass আগের ক্রম ভাঙতে পারে না। (তবে একই দলে পুরোপুরি সমান key-এর রেকর্ডের ক্রম রাখতে চাইলে ভেতরের ভাগাভাগি stable হতে হয়।)
• তাড়াতাড়ি থামে: কোনো দলে একটি মাত্র উপাদান থাকলে আর দেখার কিছু নেই। ফলে MSD প্রায়ই সব অঙ্ক দেখে না — শুধু উপাদানগুলোকে আলাদা করতে যতটুকু prefix লাগে, ততটুকু। ছোট দলে (ধরুন ১৬টির কম) অনেক বাস্তবায়ন insertion sort-এ চলে যায়, কারণ সেখানে b ঘরের cnt অ্যারে বানানোই বেশি খরচ।
• বিভিন্ন দৈর্ঘ্যের string: “bat” আর “bath”-এর মতো ক্ষেত্রে যে string আগে শেষ হয়ে যায়, তাকে একটি বিশেষ “শেষ” দলে রাখা হয় যা সবার আগে আসে — ফলে ফল হয় অভিধানের ক্রম (lexicographic order).

MSD radix sort-এর খরচ মোটামুটি Θ(D + b · (দলের সংখ্যা)), যেখানে D = সব string মিলিয়ে আলাদা করতে যত অক্ষর আসলে দেখতে হয়েছে। অনেক string-এর মধ্যে দীর্ঘ মিল থাকলে (যেমন একই prefix-এর URL) D বড় হয়, কিন্তু তবুও তুলনা-সর্টের চেয়ে ভালো থাকে, কারণ তুলনা-সর্ট প্রতিটি তুলনায় শুরু থেকে একই prefix বারবার পড়ে।

নির্দিষ্ট দৈর্ঘ্যের string-এ LSD-ও চলে। সব key সমান দৈর্ঘ্যের হলে — যেমন বিমানবন্দরের তিন অক্ষরের কোড DAC, CGP, ZYL, CXB, JSR — শেষ অক্ষর থেকে শুরু করে প্রতিটি অবস্থানে base 26 (বা ASCII-র জন্য 256) counting sort চালালে L দৈর্ঘ্যের n টি string Θ(L(n + b))-এ সাজে। পর্ব ৫৯-এ suffix array বানানোর একটি পদ্ধতিতে ঠিক এমন radix pass-ই বারবার লাগবে।

৬ · Bucket sort আর pigeonhole sort

এবার key পূর্ণসংখ্যা নয়, বাস্তব সংখ্যা: ধরুন [0, 1) পরিসরে n টি সংখ্যা, যেমন একটি এলোমেলো-সংখ্যা জেনারেটরের আউটপুট, বা ০ থেকে ১-এর মধ্যে স্বাভাবিক করা (normalized) কোনো মাপ। Counting sort এখানে চলে না — 0.3141 আর 0.3142-এর মাঝে অসীম সংখ্যা। কিন্তু যদি জানি সংখ্যাগুলো পরিসরে সমভাবে ছড়ানো (uniform distribution), তাহলে bucket sort কাজে আসে:

1. n টি খালি বালতি (bucket) নিন; বালতি i ধরবে [i/n, (i+1)/n) পরিসরের সংখ্যা।
2. প্রতিটি সংখ্যা x-কে বালতি ⌊n · x⌋-এ ফেলুন।
3. প্রতিটি বালতি আলাদাভাবে insertion sort দিয়ে সাজান (বালতিগুলো ছোট, তাই insertion sort-ই দ্রুত)।
4. বালতি 0, 1, …, n−1 পরপর জুড়ে দিন।

প্রত্যাশিত Θ(n) — একটি ছোট সম্ভাবনার হিসাব

বালতি i-তে পড়া সংখ্যার পরিমাণ nᵢ একটি random variable. Insertion sort-এ বালতির খরচ O(nᵢ²), তাই মোট খরচ Θ(n) + Σ O(nᵢ²). প্রতিটি সংখ্যা স্বাধীনভাবে 1/n সম্ভাবনায় বালতি i-তে পড়ে, তাই nᵢ একটি binomial(n, 1/n): গড় E[nᵢ] = 1, variance = 1 − 1/n. তাহলে E[nᵢ²] = Var + (E[nᵢ])² = 2 − 1/n. n টি বালতিতে যোগ করলে প্রত্যাশিত মোট খরচ Θ(n) + n · O(2 − 1/n) = Θ(n). (এটি পর্ব ০৫-এর average-case বিশ্লেষণ — গড় নেওয়া হচ্ছে ইনপুটের বণ্টনের ওপর, অ্যালগরিদমের কোনো random পছন্দের ওপর নয়। Randomized অ্যালগরিদমের expected running time থেকে এটি আলাদা: সেখানে যেকোনো ইনপুটেই গড় খাটে।)

Worst case Θ(n²), যেমন ধাপ ৬-এ দেখলেন। বালতির ভেতরে insertion sort-এর বদলে merge sort দিলে worst case নামে Θ(n log n)-এ — কিন্তু ছোট বালতিতে বাড়তি খরচ বাড়ে। জায়গা Θ(n) (বালতিগুলোর তালিকা)। বালতির ভেতরের সর্ট stable হলে, আর বালতিতে আসার ক্রমে রাখলে, পুরো bucket sort-ও stable.

Pigeonhole sort — প্রতিটি খোপে একটি তালিকা

Pigeonhole sort হলো counting sort-এর সবচেয়ে সরল আত্মীয়: key-এর পরিসর m = max − min + 1 হলে m টি খোপ নিন, প্রতিটি খোপ একটি তালিকা। প্রতিটি রেকর্ডকে তার key-এর খোপে যোগ করুন, তারপর খোপগুলো ক্রমে পড়ুন। সময় ও জায়গা Θ(n + m), stable (যদি খোপে আসার ক্রমে রাখেন)। Counting sort যেখানে শুধু সংখ্যা গোনে আর prefix sum দিয়ে ঠিকানা বের করে, pigeonhole সরাসরি রেকর্ডগুলোই খোপে রাখে — বোঝা সহজ, কিন্তু অনেক ছোট তালিকার বাড়তি মেমরি খরচ আছে। পর্ব ০৬-এর pigeonhole principle-এর সাথে নামের মিল, কাজের মিল শুধু “খোপ” ভাবনায়।

বিশেষ ক্ষেত্র: যদি জানা থাকে ইনপুট 1..n-এর একটি permutation (প্রতিটি মান ঠিক একবার), তাহলে প্রতিটি x সরাসরি ঘর x − 1-এ বসে — Θ(n) সময়ে, কোনো গোনা ছাড়াই। অংশ ১-এর পরীক্ষার খাতা সাজানো ঠিক এটিই। কনটেস্টে “1..n-এর permutation দেওয়া আছে” লাইনটি প্রায়ই এই রকম একটি shortcut-এর ইঙ্গিত।

৭ · বাস্তবে — কখন এরা std::sort-কে হারায়

Θ(n) শুনলে মনে হয় সবসময় radix sort-ই চালানো উচিত। বাস্তবে C++-এর std::sort (introsort) আর Python-এর sorted (Timsort-ভিত্তিক) — দুটোই তুলনা-সর্ট, আর বেশিরভাগ কাজে এরাই ঠিক পছন্দ। কারণগুলো দেখুন:

• Radix জেতে যখন: লাখ বা কোটি সংখ্যক 32/64-bit পূর্ণসংখ্যা (বা float) সাজাতে হয়, key সরল, আর বাড়তি n ঘরের মেমরি আছে। ডেটাবেস, GPU-র লাইব্রেরি (যেমন NVIDIA-র CUB) আর গ্রাফিক্সে বহু বস্তুকে গভীরতা অনুযায়ী সাজানোর মতো কাজে radix sort প্রচলিত।
• std::sort জেতে যখন: n ছোট (কয়েক হাজারের নিচে radix-এর প্রতিটি pass-এর স্থির খরচ চোখে পড়ে); key জটিল (string, struct, বহু-স্তরের comparator); মেমরি কম (radix-এর জন্য দ্বিতীয় একটি n-ঘরের অ্যারে লাগে); অথবা key-এর পরিসর বিশাল কিন্তু n ছোট।
• মেমরির খরচ: counting আর LSD radix — দুটোই আউটপুটের জন্য আলাদা n ঘর নেয়। ১০ কোটি 8-byte সংখ্যায় সেটি বাড়তি প্রায় ৮০০ MB. In-place MSD রূপ আছে (যেমন ১৯৯৩ সালে McIlroy, Bostic ও McIlroy-এর “American flag sort”), কিন্তু সেগুলো stable নয়।
• Cache: প্রতিটি pass-এ উপাদানগুলো b টি ভিন্ন জায়গায় ছড়িয়ে লেখা হয়। b খুব বড় হলে প্রতিটি লেখা আলাদা cache line-এ পড়ে, ফলে তাত্ত্বিক সুবিধা বাস্তবে হারিয়ে যায়। এজন্যই base 2⁸–2¹¹ জনপ্রিয়।

ঋণাত্মক সংখ্যা আর float

Counting sort-এ সমাধান সোজা: min বিয়োগ করে offset (অংশ ৩-এর সতর্কবার্তা)। Radix sort-এ দুটি প্রচলিত কৌশল:

• Offset: সবকিছু থেকে min বিয়োগ করে অ-ঋণাত্মক বানান, সাজান, শেষে min যোগ করুন। খেয়াল রাখুন, x − min বড় হয়ে overflow করতে পারে (integer overflow) — 32-bit int-এ min = −2×10⁹ আর x = 2×10⁹ হলে পার্থক্য int-এ ধরে না; তখন unsigned বা 64-bit ব্যবহার করুন।
• Sign bit উল্টে দেওয়া: two's complement-এ ঋণাত্মক সংখ্যার সবচেয়ে বাঁয়ের bit 1, তাই unsigned হিসেবে দেখলে সেগুলো ধনাত্মকের পরে আসে। key = (unsigned)x ^ 0x80000000u করলে sign bit উল্টে যায়, আর unsigned ক্রম হুবহু signed ক্রমের সমান হয়। IEEE 754 float-এর জন্য একই রকম কৌশল: ধনাত্মক হলে শুধু sign bit উল্টান, ঋণাত্মক হলে সব bit.

৮ · AI-এর যুগে রৈখিক সর্ট — “O(n)” দাবিটি যাচাই করুন

“এটি O(n) radix sort” — AI এই কথাটি খুব আত্মবিশ্বাসের সাথে বলে, অথচ প্রায়ই d আর b-কে হিসাব থেকে বাদ দেয়, অথবা k-কে ধ্রুবক ধরে নেয় যেখানে k আসলে 10⁹. আরও বিপজ্জনক ভুলগুলো কোডে লুকিয়ে থাকে: বসানোর লুপ বাঁ থেকে ডানে (stability নষ্ট — কিন্তু শুধু সংখ্যা সাজালে ফল একই দেখায়, তাই ধরা পড়ে না), ঋণাত্মক সংখ্যায় index ভুল, বা prefix sum-এ এক ঘরের off-by-one ভুল।

রৈখিক সর্টের কোডে AI সাধারণত যেসব ভুল করে

রৈখিক সর্টের কোড যাচাইয়ের চেকলিস্ট

• (key, id) জোড়া দিয়ে stability যাচাই করেছি — সমান key-এর id আগের ক্রমে আছে
• Edge case চালিয়েছি: খালি অ্যারে, এক উপাদান, সব সমান, ঋণাত্মক, সবচেয়ে বড় সম্ভাব্য key
• ছোট একটি ইনপুটে cnt আর prefix অ্যারে খাতায় লিখে কোডের আউটপুটের সাথে মিলিয়েছি
• std::sort বা sorted-কে brute force ধরে হাজারটি এলোমেলো অ্যারেতে stress testing করেছি
• complexity-তে n, k (বা d, b) সব চলক রেখেছি, আর k-এর জন্য মেমরি কত লাগবে হিসাব করেছি
• বড় n-এ সময় মেপে দেখেছি radix আসলেই std::sort-এর চেয়ে দ্রুত কি না — অনুমানে নয়