সরল সর্টিং — bubble, selection আর insertion

১ · সর্টিং কেন — পরীক্ষার খাতা থেকে মেধাতালিকা

পরীক্ষা শেষে শিক্ষকের টেবিলে একশো খাতার একটি এলোমেলো স্তূপ। নম্বর তোলার আগে তিনি খাতাগুলো রোল নম্বর অনুযায়ী সাজিয়ে নেন। কেন? কারণ সাজানো স্তূপে রোল ৫৭-এর খাতা খুঁজতে মাঝখান থেকে শুরু করে কয়েকবারেই পৌঁছানো যায়, আর কোন রোলের খাতা নেই, তা-ও এক নজরে ধরা পড়ে। এই সাজানোর কাজটিরই নাম sorting (সর্টিং) — কিছু উপাদানকে একটি নির্দিষ্ট ক্রমে, যেমন ছোট থেকে বড়, বসানো।

সর্টিং নিজে প্রায়ই শেষ লক্ষ্য নয়; এটি অন্য কাজকে সহজ করার প্রস্তুতি। কয়েকটি উদাহরণ:

• খোঁজা: সাজানো অ্যারেতে binary search একটি মান O(log n) সময়ে খুঁজে দেয় (পর্ব ১৮)। একবার সাজাতে খরচ হয়, কিন্তু তারপর হাজারটি প্রশ্নের প্রতিটি দ্রুত।
• গ্রুপ করা: একটি দোকানের সারা মাসের bKash লেনদেন গ্রাহকের নম্বর অনুযায়ী সাজালে একই গ্রাহকের সব লেনদেন পাশাপাশি চলে আসে। তখন একবার হেঁটেই প্রত্যেকের মোট বের করা যায়।
• ডুপ্লিকেট বাদ দেওয়া: সাজানোর পর একই মানগুলো পাশাপাশি থাকে, তাই শুধু আগের উপাদানের সাথে মিলিয়েই deduplication হয় — O(n) এক যাত্রায়।
• র‍্যাংকিং: ভর্তি পরীক্ষা বা চাকরির পরীক্ষার মেধাতালিকা মানে প্রাপ্ত নম্বর অনুযায়ী বড় থেকে ছোট ক্রমে সাজানো। সমান নম্বর হলে কার নাম আগে যাবে — এই প্রশ্ন থেকেই আসে stability, যা অংশ ২-এ দেখবেন।
• আরও অনেক: median বের করা, দুটি তালিকায় মিল খোঁজা, সময়সূচি বানানো, সবচেয়ে কাছের দুটি সংখ্যা খোঁজা — সব শুরু হয় সাজানো দিয়ে।

সর্টিং সমস্যা — নিখুঁত সংজ্ঞা

পর্ব ০২-এ দেখেছেন, একটি সমস্যা বলা মানে ইনপুট আর আউটপুটের সম্পর্ক বলা। সর্টিংয়ের জন্য:

• ইনপুট: n টি উপাদানের একটি ক্রম ⟨a₁, a₂, …, a_n⟩, আর উপাদানগুলোর মধ্যে তুলনার একটি নিয়ম ≤, যাতে যেকোনো দুটি উপাদান তুলনা করা যায় আর নিয়মটি সংগতিপূর্ণ (a ≤ b আর b ≤ c হলে a ≤ c).
• আউটপুট: ইনপুটেরই একটি permutation (পুনর্বিন্যাস) ⟨a′₁, a′₂, …, a′_n⟩, যাতে a′₁ ≤ a′₂ ≤ … ≤ a′_n.

দুটি শর্তই জরুরি। শুধু “ক্রম বাড়ছে” যথেষ্ট নয় — সব উপাদান কোনো কিছু না হারিয়ে, নতুন কিছু না যোগ করে থাকতে হবে। [3, 1, 2]-এর আউটপুট [1, 1, 2] ক্রমে বাড়ছে, কিন্তু 3 হারিয়ে গেছে — এটি ভুল সর্ট। AI বা নিজের লেখা কোডে swap-এর বদলে ভুল করে শুধু একটি দিকে কপি করলে ঠিক এই বাগ হয়।

বাস্তবে আমরা প্রায়ই পুরো রেকর্ড সাজাই, শুধু সংখ্যা নয়। একজন ছাত্রের রেকর্ডে আছে রোল, নাম, নম্বর। যে অংশ দেখে সাজানো হয় (যেমন নম্বর), তার নাম sort key; বাকি অংশ key-এর সাথে সাথে চলে। তুলনার নিয়মটি কোডে দেওয়া হয় একটি comparator দিয়ে (পর্ব ১৫)।

এই পর্বের সব অ্যালগরিদম comparison sort: উপাদান সম্পর্কে তারা কেবল একটি প্রশ্নই করতে পারে — “a কি b-এর চেয়ে বড়?” তাই খরচ মাপব দুটি সংখ্যায়: তুলনার সংখ্যা আর উপাদান সরানোর সংখ্যা (swap বা shift). পর্ব ০২-এর RAM model-এ দুটিই primitive operation. পর্ব ২৪-এ দেখবেন, যেকোনো comparison sort-এর worst case-এ অন্তত প্রায় n log₂ n তুলনা লাগে; এই পর্বের সরল সর্টগুলো সাধারণত n² পর্যায়ের — কিন্তু তাদের নিজস্ব শক্তি আছে, যা পুরো পর্বে দেখবেন।

২ · দুটি জরুরি গুণ — in-place আর stable

দুটি সর্টিং অ্যালগরিদম একই ফল দিলেও তাদের আচরণে পার্থক্য থাকতে পারে। চারটি শব্দ পুরো মডিউলে বারবার আসবে:

Stability প্রথমে অপ্রয়োজনীয় মনে হতে পারে — সমান তো সমানই! কিন্তু রেকর্ড সাজালে “সমান key” মানে “সমান রেকর্ড” নয়। ধরুন একটি ক্লাসের তালিকা আগে থেকেই রোল অনুযায়ী সাজানো: রোল ১ রহিম (৭০), রোল ২ করিম (৮০), রোল ৩ সুমি (৭০), রোল ৪ নাদিয়া (৯০)। এখন নম্বর অনুযায়ী বড় থেকে ছোট সাজিয়ে মেধাতালিকা বানাতে চাই, আর নিয়ম হলো: সমান নম্বরে ছোট রোল আগে। একটি stable সর্ট এই নিয়ম আপনাআপনি মানে, কারণ রহিম শুরুতে সুমির আগে ছিল, শেষেও আগে থাকবে। নিচে দুটি পদ্ধতি পাশাপাশি দেখুন (দুটির ভেতরের কাজ অংশ ৪ ও ৫-এ বিস্তারিত):

মাল্টি-key সর্টিংয়ের একটি সুন্দর কৌশল stability-র ওপর দাঁড়িয়ে: আগে দ্বিতীয় মাপকাঠিতে (রোল) সাজান, তারপর প্রথম মাপকাঠিতে (নম্বর) একটি stable সর্ট চালান। ফল হয় “নম্বর অনুযায়ী, সমান হলে রোল অনুযায়ী”। পর্ব ২৪-এর radix sort ঠিক এই নীতিতে কাজ করে, আর পর্ব ২৫-এ লাইব্রেরির stable sort নিয়ে বিস্তারিত দেখবেন।

৩ · Bubble sort — বড়টি বুদবুদের মতো ওপরে ওঠে

কোমল পানীয়ের গ্লাসে বুদবুদ নিচ থেকে ধীরে ধীরে ওপরে ওঠে। Bubble sort-এ বড় সংখ্যাগুলো ঠিক এভাবে অ্যারের ডান প্রান্তের দিকে “ভেসে” যায়। নিয়মটি সরল: বাঁ থেকে ডানে পাশাপাশি প্রতিটি জোড়া দেখুন; বাঁয়েরটি বড় হলে দুটির জায়গা বদল (swap) করুন। একবার পুরো অ্যারে ঘুরে আসাকে বলে একটি পাস। প্রথম পাস শেষে সবচেয়ে বড় উপাদানটি নিশ্চিতভাবে শেষ ঘরে পৌঁছায় — কারণ যেখানেই থাকুক, প্রতিটি তুলনায় সে জিতে ডানে এগোয়।

Pseudocode — bubble sort with early exit (0-based)

for i = 0 .. n-2:                       // pass i; the last i cells are already final
    swapped = false
    for j = 0 .. n-2-i:
        if a[j] > a[j+1]:
            swap a[j], a[j+1]
            swapped = true
    if not swapped: stop                // a pass with no swap: the array is sorted

ভেতরের লুপ কেন n-2-i পর্যন্ত? কারণ i টি পাসের পর শেষের i টি ঘরে সবচেয়ে বড় i টি উপাদান ঠিক জায়গায় বসে গেছে; সেগুলো আর দেখার দরকার নেই। [5, 2, 4, 1, 3]-এ চালিয়ে দেখুন (বন্ধনীর ভেতরের অংশ = চূড়ান্ত জায়গায় বসা):

Early exit — সাজানো ইনপুটে Θ(n)

swapped flag না থাকলে bubble sort সবসময় n − 1টি পাস চালায়, ইনপুট আগে থেকে সাজানো হলেও — অর্থাৎ সবসময় n(n − 1)/2 তুলনা, Θ(n²). Flag থাকলে একটি পাসে কোনো swap না হলেই থামা যায়। কেন নিরাপদ? কারণ swap না হওয়া মানে ওই পাসের প্রতিটি পাশাপাশি জোড়া a[j] ≤ a[j+1], আর পেছনের চূড়ান্ত অংশ আগে থেকেই সাজানো ও বড় — পুরো অ্যারেই তাহলে সাজানো। সাজানো ইনপুটে প্রথম পাসেই কোনো swap নেই: মাত্র n − 1 তুলনা, best case Θ(n).

বিশ্লেষণ

• Swap: প্রতিটি swap পাশাপাশি একটি উল্টো জোড়া ঠিক করে, তাই ঠিক একটি inversion কমায় (পর্ব ০৫)। শেষে inversion শূন্য — অতএব মোট swap = I, ইনপুটের inversion সংখ্যা। উল্টো ইনপুটে I = n(n − 1)/2; এলোমেলো ইনপুটে গড়ে n(n − 1)/4.
• তুলনা: worst case (উল্টো ইনপুট) n(n − 1)/2 = Θ(n²); best case n − 1; এলোমেলো ইনপুটেও সাধারণত প্রায় সব পাস লাগে, তাই গড়ে Θ(n²).
• জায়গা: কয়েকটি ভ্যারিয়েবল মাত্র — in-place, O(1) auxiliary space.
• Stable: হ্যাঁ — শুধু কঠোরভাবে বড় হলে (>) swap করে, আর শুধু পাশাপাশি; সমান দুটি উপাদান কখনো একে অপরকে টপকায় না। >= লিখলে stability নষ্ট হয়।

কেন সঠিক — loop invariant

পর্ব ০৩-এর তিন ধাপের loop invariant পদ্ধতি এখানে প্রয়োগ করি। বাইরের লুপের invariant: পাস i শুরুর সময় শেষের i টি ঘর a[n−i..n−1]-এ অ্যারের সবচেয়ে বড় i টি উপাদান সাজানো ক্রমে আছে।

• শুরু (i = 0): শেষের ০টি ঘর — বক্তব্যটি ফাঁকা অর্থে সত্য।
• বজায় থাকা: পাস চলার সময় ভেতরের invariant হলো “j-তম তুলনার পর a[j+1] হলো a[0..j+1]-এর সর্বোচ্চ”। তাই পাস শেষে a[n−1−i]-তে বসে বাকি অংশের সর্বোচ্চ উপাদান, যা আগের i টির চেয়ে বড় নয় — শেষের i + 1টি ঘর এখন সবচেয়ে বড় i + 1টি উপাদান, সাজানো।
• শেষ: n − 1টি পাস শেষে শেষের n − 1টি ঘর ঠিক; বাকি একটি ঘরে সবচেয়ে ছোটটি — পুরো অ্যারে সাজানো। আগে থামলে (early exit) কেন সঠিক, তা ওপরে দেখেছেন। আর প্রতিটি কাজ একটি swap, তাই আউটপুট ইনপুটেরই permutation.

৪ · Selection sort — প্রতিবার সবচেয়ে ছোটটি বেছে নেওয়া

স্কুলের অ্যাসেম্বলিতে শিক্ষক ছাত্রদের উচ্চতা অনুযায়ী লাইনে দাঁড় করাচ্ছেন। একটি সহজ পদ্ধতি: পুরো লাইনে তাকিয়ে সবচেয়ে খাটো জনকে খুঁজে প্রথম জায়গায় আনুন (সেখানে যে ছিল, সে চলে যাবে খাটো জনের পুরোনো জায়গায়)। তারপর বাকিদের মধ্যে সবচেয়ে খাটোকে দ্বিতীয় জায়গায়, এভাবে চলতে থাকুক। এটিই selection sort: প্রতি ধাপে বাকি অংশ থেকে সর্বনিম্নটি বেছে নেওয়া (select) আর একটি swap-এ তাকে ঠিক জায়গায় বসানো।

Pseudocode — selection sort (0-based)

for i = 0 .. n-2:
    m = i                              // index of the smallest seen so far
    for j = i+1 .. n-1:
        if a[j] < a[m]: m = j
    if m != i: swap a[i], a[m]         // at most one swap per position

বিশ্লেষণ — তুলনা স্থির, swap কম

i-তম ধাপে ভেতরের লুপ n − 1 − i বার তুলনা করে, ইনপুট যেমনই হোক। তাই মোট তুলনা

(n − 1) + (n − 2) + … + 1 = n(n − 1)/2

— best, average, worst সব case-এ হুবহু এক, Θ(n²). অর্থাৎ selection sort adaptive নয়: সাজানো অ্যারে দিলেও প্রতিটি সর্বনিম্ন খুঁজতে পুরো বাকি অংশ দেখে, কারণ না দেখলে নিশ্চিত হওয়ার উপায় নেই।

কিন্তু swap প্রতি ধাপে সর্বোচ্চ একটি, মোট সর্বোচ্চ n − 1 — Θ(n). উল্টো অ্যারেতে আরও মজার: [8, 7, …, 1]-এ প্রথম swap 8 আর 1 দুজনকেই ঠিক জায়গায় পাঠায়, তাই মাত্র n/2 = ৪টি swap লাগে। Bubble বা insertion sort-এ সরানোর সংখ্যা inversion-এর সমান, যা Θ(n²) পর্যন্ত যায়। তাই যেখানে লেখা দামি — বড় রেকর্ড সরানো, বা এমন মেমরি যেখানে প্রতিটি লেখা হার্ডওয়্যার ক্ষয় করে (flash memory) — সেখানে selection sort-এর এই গুণ কাজে লাগে। গুদামে ভারী চালের বস্তা সাজানোর মতো ভাবুন: চোখে দেখা (তুলনা) সস্তা, কিন্তু প্রতিটি বস্তা তোলা (swap) কষ্টের — তাই বেশি দেখে কম তোলাই বুদ্ধিমানের।

কেন সঠিক — loop invariant

Invariant: ধাপ i শুরুর সময় a[0..i−1]-এ অ্যারের সবচেয়ে ছোট i টি উপাদান সাজানো ক্রমে আছে, আর a[0..i−1]-এর প্রতিটি উপাদান a[i..n−1]-এর প্রতিটির চেয়ে ছোট বা সমান।

• শুরু (i = 0): বাঁয়ের অংশ ফাঁকা — সত্য।
• বজায় থাকা: ভেতরের লুপ শেষে a[m] হলো a[i..n−1]-এর সর্বনিম্ন (ভেতরের invariant: “m হলো a[i..j−1]-এর সর্বনিম্নের index”). swap-এ সেটি a[i]-তে বসে। এটি বাকি সবার চেয়ে ছোট বা সমান, আর বাঁয়ের অংশের সবার চেয়ে বড় বা সমান (দ্বিতীয় শর্ত থেকে) — তাই a[0..i] এখন সবচেয়ে ছোট i + 1টি, সাজানো।
• শেষ (i = n − 1): a[0..n−2] সাজানো আর a[n−1]-এর চেয়ে ছোট বা সমান — পুরো অ্যারে সাজানো।

Stable নয় — নিজের চোখে দেখুন

অংশ ২-এর stepper-এ দেখেছেন, দূরের swap সমান উপাদানকে টপকে যায়। সবচেয়ে ছোট উদাহরণ [2a, 2b, 1]: প্রথম ধাপে 1 আর 2_a-এর swap → [1, 2b, 2a] — দুটি 2-এর ক্রম উল্টে গেল। নিচের প্রোগ্রামে সেই মেধাতালিকা তিনভাবে বানানো হয়েছে, C++-এর লাইব্রেরি std::stable_sort-সহ:

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
struct Student { int roll; const char* name; int marks; };
void show(const char* title, const vector<Student>& v) {
    printf("%-11s", title);
    for (const auto& s : v) printf(" %d:%s(%d)", s.roll, s.name, s.marks);
    printf("\n");
}
int main() {
    const vector<Student> byRoll = {{1, "Rahim", 70}, {2, "Karim", 80}, {3, "Sumi", 70}, {4, "Nadia", 90}};
    vector<Student> a = byRoll;                       // selection sort, highest marks first
    for (size_t i = 0; i + 1 < a.size(); ++i) {
        size_t m = i;
        for (size_t j = i + 1; j < a.size(); ++j) if (a[j].marks > a[m].marks) m = j;
        swap(a[i], a[m]);                             // the long jump that can break ties
    }
    show("selection", a);
    vector<Student> b = byRoll;                       // insertion sort, highest marks first
    for (size_t i = 1; i < b.size(); ++i) {
        Student key = b[i]; size_t j = i;
        while (j > 0 && b[j - 1].marks < key.marks) { b[j] = b[j - 1]; --j; }   // strict <
        b[j] = key;
    }
    show("insertion", b);
    vector<Student> c = byRoll;
    stable_sort(c.begin(), c.end(), [](const Student& x, const Student& y) { return x.marks > y.marks; });
    show("stable_sort", c);
}

selection   4:Nadia(90) 2:Karim(80) 3:Sumi(70) 1:Rahim(70)
insertion   4:Nadia(90) 2:Karim(80) 1:Rahim(70) 3:Sumi(70)
stable_sort 4:Nadia(90) 2:Karim(80) 1:Rahim(70) 3:Sumi(70)

৫ · Insertion sort — তাসের মতো ঠিক জায়গায় ঢোকানো

তাস খেলায় একটি করে কার্ড তুলে আমরা হাতের আগের সাজানো কার্ডগুলোর মধ্যে তার ঠিক জায়গা খুঁজে ঢুকিয়ে দিই। লাইব্রেরিয়ান ফেরত আসা বই তাকের ঠিক জায়গায় রাখেন — ডানের বইগুলো একটু সরিয়ে ফাঁক বানিয়ে। Insertion sort এটাই করে: অ্যারের বাঁ অংশ a[0..i−1] সবসময় সাজানো; নতুন উপাদান a[i]-কে (key) সেখানে তার জায়গায় বসাতে, key-এর চেয়ে বড় উপাদানগুলোকে এক ঘর করে ডানে সরানো (shift) হয়।

Pseudocode — insertion sort (0-based)

for i = 1 .. n-1:
    key = a[i]; j = i
    while j > 0 and a[j-1] > key:     // strict >: equal keys are never passed
        a[j] = a[j-1]                  // shift one cell to the right
        j = j - 1
    a[j] = key

বিশ্লেষণ — Θ(n + I)

পর্ব ০৫-এর অংশ ৩-এ প্রমাণ করা হয়েছে: প্রতিটি shift পাশাপাশি একটি উল্টো জোড়া ঠিক করে, তাই ঠিক একটি inversion কমায়। ফলে মোট shift = I. প্রতিটি key-এর জন্য তুলনা = তার shift + ১ (থামার তুলনা), যদি না key সামনে পৌঁছে যায় (তখন থামার তুলনা লাগে না)। তাই

I ≤ তুলনা ≤ I + (n − 1), আর মোট সময় Θ(n + I).

ওপরের উদাহরণে: I + (n − 1) − (সামনে পৌঁছানো key) = 7 + 4 − 2 = 9 ✓. এখান থেকে তিন case সরাসরি:

• সাজানো ইনপুট: I = 0 → n − 1 তুলনা, ০ shift — Θ(n).
• উল্টো ইনপুট: I = n(n − 1)/2 → Θ(n²).
• এলোমেলো ইনপুট: গড় I = n(n − 1)/4 (প্রতিটি জোড়া অর্ধেক সম্ভাবনায় উল্টো), তাই গড়ে প্রায় n²/4 তুলনা — average case Θ(n²), কিন্তু bubble আর selection-এর প্রায় n²/2-এর অর্ধেক।
• প্রায়-সাজানো ইনপুট: প্রতিটি উপাদান তার আসল জায়গা থেকে সর্বোচ্চ k ঘর দূরে থাকলে I ≤ nk, তাই O(nk) — k ছোট হলে প্রায় রৈখিক।

এই কারণেই insertion sort হলো আসল অর্থে adaptive: খরচ ইনপুটের “এলোমেলোতার” (inversion) সাথে সরাসরি সমানুপাতিক। এটি stable (কঠোর >), in-place (O(1) বাড়তি জায়গা), আর online — নতুন উপাদান এলে শুধু তাকে ঢোকালেই চলে। আরেকটি বাস্তব সুবিধা: shift মানে একটি লেখা, কিন্তু swap মানে তিনটি (temp-এর মাধ্যমে)। তাই একই I-তে insertion sort bubble sort-এর চেয়ে প্রায় তিন গুণ কম লেখে।

কেন সঠিক — loop invariant

Invariant: বাইরের লুপের ধাপ i শুরুর সময় a[0..i−1]-এ ঠিক সেই উপাদানগুলো আছে যা শুরুতে a[0..i−1]-এ ছিল, কিন্তু সাজানো ক্রমে। (খেয়াল করুন, selection sort-এর মতো “চূড়ান্ত” নয় — পরে আসা ছোট উপাদান এদের ডানে ঠেলে দিতে পারে।)

• শুরু (i = 1): a[0..0] একটি উপাদান — সাজানো।
• বজায় থাকা: while লুপ key-এর চেয়ে বড় সব উপাদানকে এক ঘর ডানে সরায়, আর থামে প্রথম ছোট-বা-সমান উপাদানে বা শুরুতে। key সেই ফাঁকে বসে — বাঁয়ের সবাই ≤ key < ডানের সরানো সবাই। a[0..i] তাই সাজানো, আর উপাদানগুলো একই (শুধু সরানো হয়েছে)।
• শেষ (i = n): a[0..n−1] পুরো অ্যারে, সাজানো। পর্ব ০৩-এ এই প্রমাণটি আরও বিস্তারিতভাবে করা আছে।

৬ · তিনটি সর্ট, একই ইনপুট — তুলনা আর swap গুনে দেখা

তত্ত্বে যা বললাম, এবার মেপে দেখি। নিচের প্রোগ্রাম তিনটি সর্টকে চারটি স্থির ৮-উপাদানের অ্যারেতে চালায় — এলোমেলো-দেখতে, সাজানো, উল্টো আর প্রায়-সাজানো (দুটি পাশাপাশি জোড়া উল্টো)। প্রতিটি তুলনা যায় gt() ফাংশনের ভেতর দিয়ে, যা একটি counter বাড়ায় — নিজের কোডে অ্যালগরিদমের খরচ মাপার এটিই সবচেয়ে সৎ উপায় (benchmarking-এর মতো সময় মাপলে মেশিনের গতি মিশে যায়, গুনলে শুধু অ্যালগরিদম)।

#include <cstdio>
#include <vector>
using namespace std;
int c, s;  bool gt(int x, int y) { ++c; return x > y; }    // c counts every comparison, s every move
void bubble(vector<int> a) {
    for (int i = 0, n = a.size(); i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; ++j)
            if (gt(a[j], a[j + 1])) { swap(a[j], a[j + 1]); ++s; swapped = true; }
        if (!swapped) break;                     // a pass with no swap: already sorted
    }
}
void selection(vector<int> a) {
    for (int i = 0, n = a.size(); i < n - 1; ++i) {
        int m = i; for (int j = i + 1; j < n; ++j) if (gt(a[m], a[j])) m = j;
        if (m != i) { swap(a[i], a[m]); ++s; }
    }
}
void insertion(vector<int> a) {
    for (int i = 1, n = a.size(); i < n; ++i) {
        int key = a[i], j = i;
        while (j > 0 && gt(a[j - 1], key)) { a[j] = a[j - 1]; --j; ++s; }   // shift right
        a[j] = key;
    }
}
void run(void (*f)(vector<int>), const vector<int>& a, const char* label, const char* what) {
    c = s = 0; f(a); printf("  %-9s  comparisons = %2d  %s = %d\n", label, c, what, s); }
int main() {
    vector<pair<const char*, vector<int>>> tests = {{"random", {5, 1, 4, 8, 2, 7, 3, 6}},
        {"sorted", {1, 2, 3, 4, 5, 6, 7, 8}}, {"reversed", {8, 7, 6, 5, 4, 3, 2, 1}}, {"nearly", {1, 2, 4, 3, 5, 6, 8, 7}}};
    for (const auto& [name, a] : tests) {
        printf("%s\n", name); run(bubble, a, "bubble", "swaps");
        run(selection, a, "selection", "swaps"); run(insertion, a, "insertion", "shifts");
    }
}

random
  bubble     comparisons = 25  swaps = 12
  selection  comparisons = 28  swaps = 6
  insertion  comparisons = 18  shifts = 12
sorted
  bubble     comparisons =  7  swaps = 0
  selection  comparisons = 28  swaps = 0
  insertion  comparisons =  7  shifts = 0
reversed
  bubble     comparisons = 28  swaps = 28
  selection  comparisons = 28  swaps = 4
  insertion  comparisons = 28  shifts = 28
nearly
  bubble     comparisons = 13  swaps = 2
  selection  comparisons = 28  swaps = 2
  insertion  comparisons =  9  shifts = 2

cnt = [0, 0]                             # [comparisons, swaps or shifts]
def gt(x, y):                            # every comparison goes through here
    cnt[0] += 1
    return x > y
def bubble(a):
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if gt(a[j], a[j + 1]):
                a[j], a[j + 1] = a[j + 1], a[j]
                cnt[1] += 1; swapped = True
        if not swapped: break            # a pass with no swap: already sorted
def selection(a):
    n = len(a)
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if gt(a[m], a[j]): m = j
        if m != i:
            a[i], a[m] = a[m], a[i]; cnt[1] += 1
def insertion(a):
    for i in range(1, len(a)):
        key, j = a[i], i
        while j > 0 and gt(a[j - 1], key):
            a[j] = a[j - 1]; j -= 1; cnt[1] += 1   # shift right
        a[j] = key
tests = [("random", [5, 1, 4, 8, 2, 7, 3, 6]), ("sorted", [1, 2, 3, 4, 5, 6, 7, 8]),
         ("reversed", [8, 7, 6, 5, 4, 3, 2, 1]), ("nearly", [1, 2, 4, 3, 5, 6, 8, 7])]
for name, a in tests:
    print(name)
    for f, what in ((bubble, "swaps"), (selection, "swaps"), (insertion, "shifts")):
        cnt[:] = [0, 0]; f(a[:])         # sort a copy
        print(f"  {f.__name__:9}  comparisons = {cnt[0]:2}  {what} = {cnt[1]}")

random
  bubble     comparisons = 25  swaps = 12
  selection  comparisons = 28  swaps = 6
  insertion  comparisons = 18  shifts = 12
sorted
  bubble     comparisons =  7  swaps = 0
  selection  comparisons = 28  swaps = 0
  insertion  comparisons =  7  shifts = 0
reversed
  bubble     comparisons = 28  swaps = 28
  selection  comparisons = 28  swaps = 4
  insertion  comparisons = 28  shifts = 28
nearly
  bubble     comparisons = 13  swaps = 2
  selection  comparisons = 28  swaps = 2
  insertion  comparisons =  9  shifts = 2

৭ · চোখে দেখা — তিন সর্টের দৌড়

সংখ্যা দেখা এক জিনিস, চোখের সামনে উপাদান নড়তে দেখা আরেক। নিচের টুলে একই অ্যারে তিনটি সর্ট একসাথে সাজায় — প্রতি টিকে প্রত্যেকে একটি করে কাজ (একটি তুলনা বা একটি swap/shift) করে। তাই যে আগে শেষ করে, সে সত্যিই কম কাজ করেছে। হলুদ দণ্ড = এখন তুলনা হচ্ছে, লাল = এখন সরানো হলো, সবুজ = শেষ। ইনপুট বদলে “আবার দৌড়” চাপুন: সাজানো ইনপুটে selection sort কীভাবে একা পিছিয়ে পড়ে, আর উল্টো ইনপুটে কীভাবে সে-ই সবচেয়ে কম swap করে — দেখুন। (Insertion sort-এর shift এখানে key-কে বাঁয়ের প্রতিবেশীর সাথে জায়গা বদল হিসেবে আঁকা হয়েছে; গোনা আর ফল একই।)

// Bubble, selection and insertion race on one array: one comparison or one move per tick
const SETS = { fixed: [5, 1, 4, 8, 2, 7, 3, 6], sorted: [1, 2, 3, 4, 5, 6, 7, 8], reversed: [8, 7, 6, 5, 4, 3, 2, 1], nearly: [1, 2, 4, 3, 5, 6, 8, 7] };
const ALGS = ["bubble", "selection", "insertion"], $ = id => document.getElementById(id); let timer = 0;
function record(alg, src) {               // events: ["c" or "s", i, j, snapshot of the array]
  const a = src.slice(), ev = [], n = a.length;
  const gt = (i, j) => (ev.push(["c", i, j, a.slice()]), a[i] > a[j]);
  const sw = (i, j) => { [a[i], a[j]] = [a[j], a[i]]; ev.push(["s", i, j, a.slice()]); };
  if (alg === "bubble") for (let i = 0, any = true; any && i < n - 1; i++)   // early exit
    { any = false; for (let j = 0; j < n - 1 - i; j++) if (gt(j, j + 1)) { sw(j, j + 1); any = true; } }
  if (alg === "selection") for (let i = 0; i < n - 1; i++)
    { let m = i; for (let j = i + 1; j < n; j++) if (gt(m, j)) m = j; if (m !== i) sw(i, m); }
  if (alg === "insertion") for (let i = 1; i < n; i++) for (let j = i; j > 0 && gt(j - 1, j); j--) sw(j - 1, j);
  return ev;
}
function draw(k, kind, i, j, arr, cnt) {
  $("b" + k).innerHTML = arr.map((v, x) => `<i class="${kind === "d" || x === i || x === j ? kind : ""}" style="height:${8 + v * 7}px"></i>`).join("");
  $("t" + k).textContent = `${ALGS[k]}: comparisons ${cnt[0]}, ${k === 2 ? "shifts" : "swaps"} ${cnt[1]}`;
}
function race(arr) {
  clearInterval(timer); const evs = ALGS.map(g => record(g, arr)), pos = [0, 0, 0], cnt = [[0, 0], [0, 0], [0, 0]];
  ALGS.forEach((_, k) => draw(k, "", -1, -1, arr, cnt[k]));
  timer = setInterval(() => {
    let busy = false; evs.forEach((ev, k) => {
      if (pos[k] === ev.length) { pos[k]++; draw(k, "d", -1, -1, ev[ev.length - 1][3], cnt[k]); }
      if (pos[k] >= ev.length) return;
      const [kind, i, j, snap] = ev[pos[k]++]; cnt[k][kind === "c" ? 0 : 1]++; busy = true; draw(k, kind, i, j, snap, cnt[k]);
    });
    if (!busy) clearInterval(timer);
  }, 1100 - 100 * $("sp").value);
}
const shuffled = () => Array.from({ length: 12 }, (_, i) => i + 1).sort(() => Math.random() - 0.5);
$("go").onclick = () => race($("set").value === "random" ? shuffled() : SETS[$("set").value]);
for (const [nm, arr] of Object.entries(SETS))
  console.log(nm.padEnd(8), ALGS.map(g => { const ev = record(g, arr), c = ev.filter(e => e[0] === "c").length; return `${g} ${c}/${ev.length - c}`; }).join("  "));
race(SETS.fixed);

fixed    bubble 25/12  selection 28/6  insertion 18/12
sorted   bubble 7/0  selection 28/0  insertion 7/0
reversed bubble 28/28  selection 28/4  insertion 28/28
nearly   bubble 13/2  selection 28/2  insertion 9/2

৮ · Shell sort — দূরের উপাদানকে আগে কাছে আনা

Insertion sort-এর দুর্বলতা হলো এটি উপাদানকে একবারে মাত্র এক ঘর সরায়। উল্টো অ্যারের শেষের 1-কে সামনে আনতে n − 1টি shift. ১৯৫৯ সালে Donald L. Shell Communications of the ACM-এ “A High-Speed Sorting Procedure” প্রবন্ধে একটি সহজ সমাধান দেন: আগে দূরের উপাদানগুলোকে সাজিয়ে নিন। একটি gap h বেছে নিন, আর প্রতিটি h দূরত্বের উপাদানের সারিকে (a[0], a[h], a[2h], … একটি সারি; a[1], a[1+h], … আরেকটি) আলাদাভাবে insertion sort করুন — একে বলে h-sorting. তারপর ছোট gap, আরও ছোট, শেষে gap = 1, যা সাধারণ insertion sort. এই হলো Shell sort.

শেষ ধাপ যেহেতু পুরো insertion sort, ফল সবসময় সঠিক। লাভ হলো, বড় gap-এর ধাপগুলো এক লাফে অনেক inversion দূর করে, ফলে শেষ ধাপের কাছে আসে প্রায়-সাজানো অ্যারে — আর প্রায়-সাজানো অ্যারেতে insertion sort দ্রুত (অংশ ৫)। উল্টো অ্যারে [8, 7, 6, 5, 4, 3, 2, 1]-এ Shell-এর নিজের ধারা অনুযায়ী gap n/2 = 4, তারপর 2, তারপর 1 দিয়ে দেখুন:

// Shell sort with Knuth's gaps 1, 4, 13, 40, ... (h = 3h + 1)
void shellSort(vector<int>& a) {
    int n = a.size(), h = 1;
    while (h < n / 3) h = 3 * h + 1;              // largest gap below n/3
    for (; h >= 1; h /= 3)                         // ..., 40, 13, 4, 1
        for (int i = h; i < n; ++i) {              // insertion sort on every h-chain
            int key = a[i], j = i;
            for (; j >= h && a[j - h] > key; j -= h) a[j] = a[j - h];
            a[j] = key;
        }
}

Gap-এর ধারা — কোনটি ভালো?

Shell sort-এর গতি পুরোপুরি নির্ভর করে gap sequence-এর ওপর, আর এটি আজও গবেষণার বিষয়:

সংখ্যার একটি অনুভূতি: আমাদের একটি পরীক্ষায় ১০,০০০টি এলোমেলো সংখ্যায় Knuth-এর gap দিয়ে Shell sort প্রায় ২.৫ লাখ তুলনা করেছে, আর সাধারণ insertion sort প্রায় ২.৫ কোটি — প্রায় একশো গুণ পার্থক্য। Shell sort in-place (O(1) বাড়তি জায়গা), রিকার্শন নেই, কোড ছোট — তাই ছোট মেমরির embedded সিস্টেমে এটি এখনো বেছে নেওয়া হয়। তবে এটি stable নয়: দূরের লাফ সমান উপাদানকে টপকে যায়, ঠিক selection sort-এর মতো।

৯ · পাশাপাশি তুলনা — কখন কোনটি

তিনটি invariant এক নজরে

পর্ব ০৩-এর ভাষায়, তিনটি অ্যালগরিদমের পার্থক্য আসলে তাদের invariant-এর পার্থক্য। খাতায় লেখার মতো করে:

• Bubble: i টি পাসের পর ডানের i টি ঘরে সবচেয়ে বড় i টি, চূড়ান্ত জায়গায়।
• Selection: i টি ধাপের পর বাঁয়ের i টি ঘরে সবচেয়ে ছোট i টি, চূড়ান্ত জায়গায়।
• Insertion: i টি ধাপের পর বাঁয়ের i + 1টি ঘরে শুরুর সেই একই উপাদানগুলো, সাজানো — কিন্তু চূড়ান্ত নয়।

একটি পরীক্ষার কৌশল: কোনো অজানা সর্টের মাঝপথের অবস্থা দেওয়া থাকলে এই invariant দিয়েই চেনা যায়, এটি কোন সর্ট। যেমন [2, 4, 5, 1, 3]-কে [5, 2, 4, 1, 3]-এর মাঝপথ হিসেবে দেখালে — বাঁয়ের 2 4 5 সাজানো কিন্তু ছোট উপাদান 1 এখনো ডানে — এটি insertion sort-এর দুই ধাপ পরের অবস্থা; selection sort হলে প্রথম ঘরে 1 থাকত।

কখন কোনটি বেছে নেবেন

আর n বড় হলে (হাজার বা লাখ) এদের কোনোটিই নয় — তখন Θ(n log n)-এর merge sort (পর্ব ২১), quick sort (পর্ব ২২), heapsort (পর্ব ২৩) বা ভাষার লাইব্রেরির sort (পর্ব ২৫)। মজার বিষয়, সেই বড় অ্যালগরিদমগুলোর ভেতরেও insertion sort লুকিয়ে থাকে: GCC-র std::sort যে introsort ব্যবহার করে, তা ছোট টুকরো (১৬টি উপাদানের মতো) insertion sort-কে দিয়ে দেয়, আর Python-এর Timsort ছোট “run”-গুলো binary insertion sort দিয়ে বানায়। কারণ ছোট n-এ insertion sort-এর ধ্রুবক খুব ছোট: রিকার্শন নেই, বাড়তি মেমরি নেই, মেমরি পরপর পড়া হয় (cache-বান্ধব)।

১০ · AI-এর যুগে সর্টিং — চেনা কোডে অচেনা বাগ

“Bubble sort লিখে দাও” — AI এক সেকেন্ডে লিখে দেবে, আর বেশিরভাগ সময় চলবেও। কিন্তু সরল সর্টের ভুলগুলো সূক্ষ্ম: একটি > বনাম >= stability নষ্ট করে, লুপের সীমায় এক ঘরের ভুল (off-by-one) অ্যারের বাইরে পড়ে, আর complexity-র দাবি প্রায়ই অর্ধসত্য — যেমন flag ছাড়া লেখা bubble sort-কে “best case O(n)” বলা, বা Shell sort-কে নির্দ্বিধায় “O(n log n)” বলা। ছোট সুন্দর উদাহরণে এর কোনোটিই ধরা পড়ে না।

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

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

• ছোট একটি ইনপুটে খাতায় প্রতিটি পাস trace করে কোডের আউটপুটের সাথে মিলিয়েছি
• Edge case চালিয়েছি: খালি, এক উপাদান, দুই উপাদান, সব সমান, সাজানো, উল্টো
• তুলনা আর swap গোনার counter বসিয়ে সূত্রের সাথে মিলিয়েছি (যেমন selection-এ সবসময় n(n − 1)/2)
• সমান key-এর রেকর্ড দিয়ে stability পরীক্ষা করেছি
• লাইব্রেরির sort-কে brute force উত্তর ধরে হাজারটি এলোমেলো ছোট অ্যারেতে stress testing করেছি — ফল এক, আর permutation-ও
• AI-এর দেওয়া প্রতিটি complexity দাবির পেছনে কোন ইনপুট সবচেয়ে খারাপ, তা নিজে বলতে পারি