বাস্তবে সর্টিং — stable sort, comparator আর লাইব্রেরি

১ · লাইব্রেরির sort ভেতরে কী করে

পর্ব ২০ থেকে ২৪ পর্যন্ত আপনি নিজের হাতে insertion, merge, quick, heap আর counting sort লিখেছেন। কিন্তু কাজের কোডে বা কনটেস্টে প্রায় কেউই নিজে sort লেখেন না — এক লাইনে sort(v.begin(), v.end()) বা a.sort(). তাহলে এতগুলো অ্যালগরিদম শেখা কেন? কারণ লাইব্রেরির sort আসলে এই অ্যালগরিদমগুলোরই চতুর মিশ্রণ। কোনটি কখন কোনটিতে বদলায়, কোনটি stable, কোনটি বাড়তি মেমরি নেয় — এগুলো না জানলে আপনি ভুল ফাংশন বেছে নেবেন, বা ভুল comparator দিয়ে প্রোগ্রাম crash করাবেন।

C++: std::sort, std::stable_sort, std::partial_sort, std::nth_element

C++11 থেকে standard বলে দেয়, std::sort-কে worst case-এও O(n log n) তুলনায় শেষ করতে হবে। কিন্তু কোন অ্যালগরিদমে, তা বলে না। GCC-র libstdc++ (আর বেশিরভাগ বাস্তবায়ন) ব্যবহার করে introsort, যা David Musser ১৯৯৭ সালে প্রস্তাব করেন:

1. শুরুতে quick sort — median-of-3 pivot দিয়ে partition (পর্ব ২২)। গড়ে এটিই সবচেয়ে দ্রুত, আর in-place.
2. রিকার্শন বেশি গভীর হলে heapsort — গভীরতার সীমা প্রায় 2·log₂ n. সীমা পেরোনো মানে pivot বারবার খারাপ পড়ছে, quick sort O(n²)-এর দিকে যাচ্ছে। তখন সেই টুকরোটি heapsort দিয়ে শেষ হয় (পর্ব ২৩), যার worst case O(n log n).
3. ছোট টুকরোয় insertion sort — libstdc++-এ ১৬টি বা তার কম উপাদানের টুকরো quick sort আর ভাগ করে না, ফেলে রাখে। শেষে পুরো array-তে একবার insertion sort চলে। তখন প্রতিটি উপাদান তার আসল জায়গার খুব কাছে, তাই insertion sort প্রায় O(n) (পর্ব ২০).

ফল: গড়ে quick sort-এর গতি, worst case-এ heapsort-এর নিশ্চয়তা, আর ছোট টুকরোয় insertion sort-এর কম overhead. বাড়তি জায়গা শুধু রিকার্শনের stack, O(log n). কিন্তু একটি দাম আছে — std::sort stable নয়. সমান দুটি উপাদানের আগের ক্রম বদলে যেতে পারে।

Python: sorted আর list.sort — Timsort

Python-এর দুটি sort একই অ্যালগরিদম চালায়: Timsort, যা Tim Peters ২০০২ সালে Python-এর জন্য লেখেন। sorted(x) নতুন list দেয়, a.sort() জায়গাতেই সাজায় আর None ফেরত দেয়। Timsort-এর মূল ধারণা: বাস্তবের ডেটা খুব কম ক্ষেত্রেই পুরো এলোমেলো। প্রায়ই তাতে আগে থেকেই সাজানো লম্বা টুকরো থাকে — যেমন তারিখ ধরে সাজানো bKash লেনদেনের তালিকার শেষে কয়েকটি নতুন লেনদেন। এমন টুকরোকে বলে run. Timsort তিনটি কাজ করে:

• Run খোঁজা: বাঁ থেকে ডানে গিয়ে বাড়তে থাকা (non-decreasing) বা কঠোরভাবে কমতে থাকা টুকরো চিনে নেয়। কমতে থাকা run উল্টে দেয়। run খুব ছোট হলে (minrun, সাধারণত ৩২ থেকে ৬৪-এর মধ্যে) binary insertion sort দিয়ে সেটিকে minrun মাপ পর্যন্ত বড় করে।
• Run জোড়া দেওয়া: run-গুলো একটি stack-এ রাখে আর কিছু নিয়ম মেনে পাশাপাশি run-কে merge করে, যাতে মাপে কাছাকাছি run-গুলো জোড়া লাগে — merge sort-এর মতো ভারসাম্য থাকে।
• Galloping: merge-এর সময় যদি একটি run থেকে পরপর অনেকগুলো (শুরুতে ৭টি) উপাদান জেতে, Timsort একটি একটি করে তুলনা ছেড়ে 1, 3, 7, 15 …-এর মতো লাফ দিয়ে খোঁজে (exponential search), তারপর binary search. ফলে একটি run-এর বড় অংশ একসাথে কপি হয়।

ফল: পুরো সাজানো বা পুরো উল্টো ইনপুটে O(n) — মাত্র n − 1 টি তুলনা। worst case O(n log n). বাড়তি জায়গা O(n) (merge-এর বাফার)। আর এটি stable — Python-এর documentation এর নিশ্চয়তা দেয়। এমন sort, যা ইনপুটে যত বেশি ক্রম আগে থেকে আছে তত দ্রুত চলে, তাকে বলে adaptive sort.

Java আর JavaScript — সংক্ষেপে

Java দুই রকম ডেটার জন্য দুই রকম অ্যালগরিদম রাখে। int[], double[]-এর মতো primitive array-তে Arrays.sort চালায় dual-pivot quicksort (Vladimir Yaroslavskiy, Jon Bentley আর Joshua Bloch, Java 7 থেকে) — দুটি pivot নিয়ে array-কে তিন ভাগ করে। আর object-এর array বা List-এ (Collections.sort, List.sort) চালায় Timsort. কেন এই ভাগ? দুটি সমান int-কে আলাদা করে চেনার কোনো উপায় নেই — তাই সেখানে stability-র কোনো মানে নেই, শুধু গতি দরকার। কিন্তু দুটি Student object-এর নম্বর সমান হলেও তারা আলাদা মানুষ — সেখানে stability জরুরি।

JavaScript-এ ECMAScript 2019 থেকে Array.prototype.sort-কে stable হতেই হবে; V8 (Chrome, Node.js) এর জন্য Timsort ব্যবহার করে। তবে একটি পুরোনো ফাঁদ এখনো আছে: comparator না দিলে JavaScript সব উপাদানকে string বানিয়ে তুলনা করে। তাই [10, 9, 1].sort() দেয় [1, 10, 9]. সংখ্যার জন্য সবসময় লিখুন a.sort((x, y) => x - y).

২ · Stable sort — সমান হলে আগের ক্রম অটুট

পরীক্ষার হলে খাতা জমা পড়েছে রোল নম্বরের ক্রমে। এখন শিক্ষক খাতাগুলো প্রাপ্ত নম্বর অনুযায়ী সাজাবেন। দুজনের নম্বর সমান হলে কে আগে? যদি সাজানোর পদ্ধতি নিশ্চয়তা দেয় যে সমান নম্বরের খাতাগুলো আগের মতোই রোলের ক্রমে থাকবে, তাহলে সেটি stable sort. নিশ্চয়তা না দিলে — unstable — তারা যেকোনো ক্রমে আসতে পারে, আর এক রানে এক রকম, আরেক রানে আরেক রকম (pivot এলোমেলো হলে) আসাও সম্ভব।

আনুষ্ঠানিক সংজ্ঞা: যদি ইনপুটে i < j আর key(a[i]) = key(a[j]) হয়, তাহলে stable sort-এর আউটপুটে a[i] অবশ্যই a[j]-এর আগে থাকবে। খেয়াল করুন, শুধু সংখ্যা সাজালে stability চোখেই পড়ে না — দুটি 5 দেখতে এক। Stability-র প্রশ্ন ওঠে তখনই, যখন উপাদানে key ছাড়াও অন্য তথ্য থাকে: নাম, রোল, লেনদেনের সময়।

কোন sort stable, কোনটি নয় — আর কেন

• Stable: insertion sort (শুধু কঠোরভাবে বড় হলে সরায়), merge sort (merge-এ সমান হলে বাঁ দিকেরটি আগে নেয় — <= দিয়ে), counting sort আর LSD radix sort (শেষ থেকে বসালে), Timsort.
• Unstable: quick sort (partition-এ দূরের উপাদান অদলবদল হয়), heapsort (heap-এর গঠন ক্রম মনে রাখে না), selection sort (array-তে swap দূরের উপাদানকে লাফিয়ে সরায়), introsort.

যেকোনো sort-কে stable বানানোর একটি সাধারণ কৌশল আছে: প্রতিটি উপাদানের সাথে তার মূল index জুড়ে দিন, আর key সমান হলে index দিয়ে তুলনা করুন। তখন কোনো দুটি উপাদান আর “সমান” থাকে না, তাই stability-র প্রশ্নই ওঠে না। খরচ: প্রতি উপাদানে একটি বাড়তি সংখ্যা, Θ(n) জায়গা।

কয়েক ধাপে সাজানোর কৌশল (multi-pass stable sort)

Stability-র সবচেয়ে কাজের প্রয়োগ: একাধিক মাপকাঠিতে সাজানো, কোনো জটিল comparator ছাড়াই। লক্ষ্য — নম্বর বড় থেকে ছোট, নম্বর সমান হলে নাম বর্ণানুক্রমে। কৌশল হলো উল্টো দিক থেকে: আগে গৌণ key (নাম) দিয়ে সাজান, তারপর মুখ্য key (নম্বর) দিয়ে stable sort করুন। দ্বিতীয় ধাপ সমান নম্বরের ছাত্রদের ছোঁয় না — তাই প্রথম ধাপের নামের ক্রম তাদের মধ্যে টিকে থাকে।

এই কৌশলটি spreadsheet-এ আপনি না জেনেই ব্যবহার করেন: Excel বা Google Sheets-এ আগে “নাম” কলামে sort, তারপর “নম্বর” কলামে sort করলে ঠিক এই ফল পাবেন। Python-এর documentation-ও একাধিক key-তে সাজানোর একটি পথ হিসেবে এটি দেখায়, বিশেষ করে যখন একটি key বড় থেকে ছোট আর অন্যটি ছোট থেকে বড়, আর key-টি এমন যে তার আগে মাইনাস বসানো যায় না, যেমন string-এর ক্ষেত্রে।

৩ · Comparator আর strict weak ordering — <= কেন বিপদ

নিজের ক্রমে সাজাতে C++-এ comparator দিতে হয় — দুটি উপাদান নিয়ে একটি প্রশ্নের উত্তর দেওয়া ফাংশন: “a কি b-এর কঠোরভাবে আগে বসবে?” খেয়াল করুন “কঠোরভাবে” শব্দটি। এটি “a কি b-এর আগে বা সমান?” নয়। Standard অনুযায়ী comparator-কে একটি strict weak ordering হতে হবে। এর চারটি শর্ত, comp(a, b) মানে “a আগে”:

শেষ শর্তটি সূক্ষ্ম। “weak” শব্দটি এখান থেকেই: দুটি আলাদা উপাদানও “সমান” (equivalent) হতে পারে — যেমন একই নম্বরের দুজন ছাত্র — কিন্তু এই সমতা নিজে একটি ঠিকঠাক সম্পর্ক হতে হবে। একটি ভাঙা উদাহরণ: “দুটি সংখ্যার পার্থক্য ১-এর কম হলে সমান ধরো”. তাহলে 1 ~ 1.6 আর 1.6 ~ 2.2, কিন্তু 1 আর 2.2 সমান নয় — sort তখন দিশেহারা।

কেন <= শুধু ভুল ক্রম নয়, crash ঘটাতে পারে

লাইব্রেরি comparator-এর এই শর্তের ওপর ভরসা করে গতি বাড়ায়। libstdc++-এর introsort-এর শেষ ধাপে insertion sort চলে, আর প্রথম ১৬টি ঘর সাজানোর পর ধরে নেওয়া যায় যে a[0]-এ সবচেয়ে ছোট উপাদানটি আছে। তাই বাকি অংশের insertion-এ ভেতরের লুপে “j > 0 কি না” যাচাই রাখা হয় না — প্রতি ধাপে একটি তুলনা বাঁচে। লুপ থামবে, কারণ comp(val, a[0]) কখনো true হবে না: কোনো উপাদান সবচেয়ে ছোটটির কঠোরভাবে আগে বসে না। এই কৌশলের নাম unguarded insertion — a[0] এখানে একটি প্রহরী (sentinel). এবার <= দিলে কী হয়, দেখুন:

একই ব্যাপার partition-এর ভেতরের লুপেও ঘটে: “pivot-এর চেয়ে ছোট হলে এগোও” লুপটি pivot-এর সমান উপাদানে থামবে বলে ধরে নেওয়া হয়। <= দিলে সব উপাদান “ছোট” — pointer array-র শেষ পেরিয়ে চলে যায়। ছোট পরীক্ষায় (১৬টির কম উপাদান, বা কোনো সমান মান নেই) প্রোগ্রাম ঠিকঠাক চলে, তাই ভুলটি ধরা পড়ে অনেক পরে — online judge-এ runtime error হয়ে, বা কাজের সার্ভারে।

// WRONG: not irreflexive -- cmp(x, x) is true. Undefined behaviour in std::sort.
sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });
// RIGHT: strict "comes before"
sort(v.begin(), v.end(), [](int a, int b) { return a < b; });
// descending: swap the roles, never use >=
sort(v.begin(), v.end(), [](int a, int b) { return a > b; });   // or greater<int>()
// quick self-check while debugging (cmp = your comparator): no element may come before itself
for (int x : v) assert(!cmp(x, x));

৪ · একাধিক key আর নিজের struct সাজানো

বাস্তবে প্রায় কখনোই শুধু একটি সংখ্যা সাজাতে হয় না। মেধাতালিকা: নম্বর বড় থেকে ছোট, নম্বর সমান হলে রোল ছোট থেকে বড়। Daraz-এর পণ্যতালিকা: দাম ছোট থেকে বড়, দাম সমান হলে রেটিং বড় থেকে ছোট। প্রতিটি ক্ষেত্রে একটি মুখ্য key আর এক বা একাধিক tie-breaking key. দুই ভাষা এটি দুইভাবে প্রকাশ করে।

Python: key function আর tuple-এর তুলনা

Python 3-এ sort-এ comparator দেওয়ার সরাসরি উপায় নেই; দিতে হয় একটি key function — প্রতিটি উপাদান থেকে একটি মান বানায়, আর sort শুধু সেই মানগুলো তুলনা করে। key প্রতিটি উপাদানের জন্য ঠিক একবার হিসাব হয় (n বার), তুলনার প্রতিবার নয় (n log n বার) — তাই দামি key-ও সস্তা। একাধিক key-এর জন্য key একটি tuple ফেরত দেয়, কারণ Python tuple-কে lexicographic ক্রমে তুলনা করে: আগে প্রথম ঘর, সমান হলে দ্বিতীয় ঘর, এভাবে।

students.sort(key=lambda s: (-s.marks, s.roll))     # marks desc, roll asc
students.sort(key=lambda s: (s.dept, -s.marks))      # dept A-Z, then marks desc
from operator import attrgetter
students.sort(key=attrgetter("dept", "roll"))        # same idea, a bit faster
# a string key cannot be negated: use two stable passes instead
students.sort(key=lambda s: s.name)                  # secondary key first
students.sort(key=lambda s: s.dept, reverse=True)    # primary key last; reverse keeps stability
from functools import cmp_to_key                     # when only a comparator makes sense
students.sort(key=cmp_to_key(lambda a, b: (a.marks < b.marks) - (a.marks > b.marks)))

মাইনাস চিহ্নের কৌশল (-s.marks) শুধু সংখ্যায় চলে। নাম উল্টো বর্ণানুক্রমে আর বাকিটা সোজা ক্রমে চাইলে অংশ ২-এর দুই ধাপের কৌশল ব্যবহার করুন। reverse=True stability নষ্ট করে না — documentation অনুযায়ী সমান উপাদানগুলো তখনো আগের ক্রমে থাকে।

C++: comparator lambda, std::tie আর C++20-এর projection

struct Student { int roll; string name; int marks; };

// 1) explicit lambda: compare the primary key, fall through to the tie-breaker
sort(v.begin(), v.end(), [](const Student& a, const Student& b) {
    if (a.marks != b.marks) return a.marks > b.marks;   // marks desc
    return a.roll < b.roll;                             // roll asc
});
// 2) std::tie builds tuples of references; put b first for a descending key
sort(v.begin(), v.end(), [](const Student& a, const Student& b) {
    return tie(b.marks, a.roll) < tie(a.marks, b.roll);
});
// 3) C++20 ranges: comparator + projection (sort by marks, high first)
ranges::sort(v, ranges::greater{}, &Student::marks);
// 4) C++20: a default ordering for the type itself (members compared in order)
//    inside the struct:  auto operator<=>(const Student&) const = default;

উপায় ১ সবচেয়ে পরিষ্কার আর নতুনদের জন্য সবচেয়ে নিরাপদ। উপায় ২-এ std::tie সদস্যদের reference নিয়ে একটি tuple বানায়; tuple-এর < lexicographic, তাই নিজে থেকেই strict weak ordering. বড় থেকে ছোট key-এর জন্য সেই ঘরে a আর b-এর জায়গা বদলে দিন। উপায় ৩-এ projection (&Student::marks) বলে দেয় কোন সদস্য তুলনা হবে — Python-এর key-এর কাছাকাছি ধারণা। উপায় ৪-এ operator<=> “default” করলে সদস্যগুলো ঘোষণার ক্রমে তুলনা হয়; তখন সরাসরি sort(v.begin(), v.end()) চলে। Python-এ একই কাজ করে @dataclass(order=True).

৫ · String সাজানো — অভিধান, বড়-ছোট হাতের অক্ষর আর “file10”

String-এর ডিফল্ট তুলনা lexicographic (পর্ব ১১): বাঁ থেকে প্রথম যে ঘরে দুটি string আলাদা, সেই দুই অক্ষরের কোড তুলনা করে ফল ঠিক হয়; একটি অন্যটির শুরুর অংশ হলে ছোটটি আগে। এর তিনটি ফল প্রায়ই মানুষকে অবাক করে:

1. বড় হাতের অক্ষর আগে. ASCII-তে 'A'–'Z' হলো 65–90, আর 'a'–'z' হলো 97–122. তাই "Zebra" < "apple" — অভিধানের উল্টো।
2. সংখ্যা অক্ষর হিসেবে তুলনা হয়. "file10" আর "file2"-এর প্রথম পার্থক্য পঞ্চম ঘরে: '1' বনাম '2'. '1' ছোট, তাই "file10" < "file2".
3. অক্ষরের কোড মানেই ভাষার ক্রম নয়. Unicode-এর code point ক্রম ইংরেজির বাইরে অনেক ভাষার অভিধানের ক্রমের সাথে মেলে না — বাংলায় কার-চিহ্ন, হসন্ত আর যুক্তাক্ষর অভিধানে যেভাবে সাজানো থাকে, code point সেভাবে সাজায় না।

Case-insensitive sort

names = ["rahim", "Karim", "arif", "Sadia"]
sorted(names)                      # ['Karim', 'Sadia', 'arif', 'rahim']  (code order)
sorted(names, key=str.casefold)    # ['arif', 'Karim', 'rahim', 'Sadia']
sorted(names, key=lambda s: (s.casefold(), s))   # deterministic tie: "abc" vs "ABC"

auto lowerLess = [](const string& a, const string& b) {
    return lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(),
        [](unsigned char x, unsigned char y) { return tolower(x) < tolower(y); });
};
sort(names.begin(), names.end(), lowerLess);   // ASCII letters only

casefold হলো lower-এর আরও আক্রমণাত্মক রূপ, যা কিছু ভাষার বিশেষ অক্ষরও (যেমন জার্মান ß → ss) সামলায়। C++-এর tolower শুধু ASCII-র জন্য ভরসাযোগ্য, আর char-কে আগে unsigned char-এ বদলাতে হয় — ঋণাত্মক মান দিলে undefined behavior. সত্যিকারের বহুভাষিক ক্রমের জন্য Unicode Collation Algorithm মেনে চলা লাইব্রেরি (যেমন ICU) লাগে, যাকে বলে collation.

Natural sort — মানুষ যেভাবে পড়ে

আপনার ফোনে ছবির নাম IMG2.jpg, IMG10.jpg, IMG1.jpg. মানুষ চায় 1, 2, 10. কৌশল: string-কে সংখ্যা আর অ-সংখ্যার টুকরোয় ভাঙুন, সংখ্যার টুকরোকে int বানান, তারপর টুকরোর list-কে lexicographic ক্রমে তুলনা করুন।

import re
def natural_key(s):
    # "file10.txt" -> ['file', 10, '.txt']; text and numbers always alternate
    return [int(t) if t.isdigit() else t.casefold() for t in re.split(r"(\d+)", s)]

files = ["file10.txt", "file2.txt", "File3.txt", "file1.txt"]
sorted(files)                     # ['File3.txt', 'file1.txt', 'file10.txt', 'file2.txt']
sorted(files, key=natural_key)    # ['file1.txt', 'file2.txt', 'File3.txt', 'file10.txt']

re.split-এ বন্ধনীর ভেতরের pattern থাকায় সংখ্যার টুকরোগুলোও ফলাফলে থাকে, আর ফলের list-এ জোড় index-এ সবসময় লেখা, বিজোড় index-এ সবসময় সংখ্যা — তাই দুটি key তুলনার সময় কখনো str আর int মুখোমুখি হয় না (Python 3-এ সেটি TypeError দিত)। খরচ: প্রতিটি string থেকে একবার key, মোট O(L) যেখানে L সব string-এর মোট দৈর্ঘ্য; তারপর O(n log n) তুলনা, প্রতিটি তুলনা key-এর দৈর্ঘ্যের সমানুপাতিক। বাকি থাকা প্রশ্ন — "file007" আর "file7" সমান কি না, দশমিক বিন্দু, ঋণাত্মক চিহ্ন — প্রতিটি প্রয়োগে নিজে ঠিক করতে হয়।

৬ · Index সাজানো আর rank — মেধাতালিকা বানানো

Argsort — মান নয়, index সাজানো

কখনো মূল array বদলানো যায় না, বা একই index দিয়ে কয়েকটি আলাদা array (নাম, নম্বর, রোল) একসাথে মেলাতে হয়। তখন মান নয়, index-গুলো সাজান: idx-কে এমনভাবে সাজান যাতে a[idx[0]] ≤ a[idx[1]] ≤ … হয়। NumPy-তে এই কাজের নাম argsort, আর নামটি এখন সাধারণ পরিভাষা।

vector<int> a = {30, 10, 20, 10};
vector<int> idx(a.size());
iota(idx.begin(), idx.end(), 0);                         // 0 1 2 3
stable_sort(idx.begin(), idx.end(), [&](int i, int j) { return a[i] < a[j]; });
// idx = 1 3 2 0   (a[1]=10, a[3]=10, a[2]=20, a[0]=30)
vector<int> pos(a.size());
for (int k = 0; k < (int)idx.size(); ++k) pos[idx[k]] = k;  // inverse: where did i go?

a = [30, 10, 20, 10]
idx = sorted(range(len(a)), key=a.__getitem__)   # [1, 3, 2, 0]
pos = [0] * len(a)
for k, i in enumerate(idx):
    pos[i] = k                                   # pos = [3, 0, 2, 1]

idx একটি permutation (০ থেকে n−1-এর প্রতিটি সংখ্যা ঠিক একবার)। তার উল্টো permutation pos বলে, মূল i-তম উপাদান সাজানোর পর কত নম্বর ঘরে গেল। সাজাতে O(n log n), উল্টো বানাতে O(n), জায়গা Θ(n).

সমান নম্বরে rank — তিন রকম নিয়ম

মেধাতালিকায় দুজনের নম্বর সমান হলে দুজনেরই একই অবস্থান হওয়া উচিত। কিন্তু তাদের পরের জন কত? তিনটি প্রচলিত নিয়ম আছে, আর SQL-এ তিনটির জন্যই আলাদা ফাংশন:

Competition rank-এর যুক্তি: “আমার চেয়ে বেশি নম্বর পেয়েছে কতজন, তার এক বেশি” — খেলাধুলা আর অনেক মেধাতালিকা এভাবে চলে। Dense rank-এর যুক্তি: “আমার চেয়ে বেশি কতগুলো আলাদা নম্বর আছে, তার এক বেশি” — গ্রেডের স্তর বা “কততম সর্বোচ্চ নম্বর” প্রশ্নে কাজের। দুটিই সাজানোর পর একবার হেঁটে পাওয়া যায়: আগের জনের নম্বর থেকে আলাদা হলেই নতুন rank শুরু। Dense rank আসলে পরের অংশের coordinate compression-এরই আরেক চেহারা।

এবার পুরো কাজটি চালিয়ে দেখুন: সাতজন ছাত্রকে (নম্বর বড় থেকে ছোট, নম্বর সমান হলে রোল ছোট থেকে বড়) সাজানো, তারপর dense আর competition rank.

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

struct Student { int roll; string name; int marks; };

int main() {
    vector<Student> v = {{1, "Rahim", 78}, {2, "Karim", 92}, {3, "Sadia", 85},
                         {4, "Nusrat", 92}, {5, "Tanvir", 78}, {6, "Mitu", 64},
                         {7, "Arif", 85}};
    sort(v.begin(), v.end(), [](const Student& a, const Student& b) {
        if (a.marks != b.marks) return a.marks > b.marks;  // marks high to low
        return a.roll < b.roll;                            // then roll low to high
    });
    printf("dense comp roll name    marks\n");
    int dense = 0, comp = 0;
    for (size_t i = 0; i < v.size(); ++i) {
        if (i == 0 || v[i].marks != v[i - 1].marks) {      // a new mark starts a new rank
            ++dense;
            comp = (int)i + 1;
        }
        printf("%5d %4d %4d %-7s %5d\n", dense, comp, v[i].roll, v[i].name.c_str(), v[i].marks);
    }
}

dense comp roll name    marks
    1    1    2 Karim      92
    1    1    4 Nusrat     92
    2    3    3 Sadia      85
    2    3    7 Arif       85
    3    5    1 Rahim      78
    3    5    5 Tanvir     78
    4    7    6 Mitu       64

from collections import namedtuple

Student = namedtuple("Student", "roll name marks")
v = [Student(1, "Rahim", 78), Student(2, "Karim", 92), Student(3, "Sadia", 85),
     Student(4, "Nusrat", 92), Student(5, "Tanvir", 78), Student(6, "Mitu", 64),
     Student(7, "Arif", 85)]

v.sort(key=lambda s: (-s.marks, s.roll))   # marks high to low, then roll low to high

print("dense comp roll name    marks")
dense = comp = 0
for i, s in enumerate(v):
    if i == 0 or s.marks != v[i - 1].marks:  # a new mark starts a new rank
        dense += 1
        comp = i + 1
    print(f"{dense:5d} {comp:4d} {s.roll:4d} {s.name:<7s} {s.marks:5d}")

dense comp roll name    marks
    1    1    2 Karim      92
    1    1    4 Nusrat     92
    2    3    3 Sadia      85
    2    3    7 Arif       85
    3    5    1 Rahim      78
    3    5    5 Tanvir     78
    4    7    6 Mitu       64

৭ · Coordinate compression — বড় মানকে ছোট index-এ আনা

ধরুন n = 2 × 10⁵ টি সংখ্যা, প্রতিটি −10⁹ থেকে 10⁹-এর মধ্যে। প্রতিটি মান কতবার এসেছে গুনতে চান, বা পরে পর্ব ৩৬-এর Fenwick tree-তে মানগুলোকে index হিসেবে বসাতে চান। মানের সমান মাপের array (২০০ কোটি ঘর) বানানো অসম্ভব। কিন্তু খেয়াল করুন: আলাদা মান আছে সর্বোচ্চ n টি। আর অনেক সমস্যায় মানের আসল পরিমাণ গুরুত্বপূর্ণ নয় — শুধু কে কার চেয়ে ছোট, সেটুকু। তাহলে প্রতিটি মানকে তার “আলাদা মানগুলোর মধ্যে অবস্থান” দিয়ে বদলে দিন: সবচেয়ে ছোটটি 0, তার পরেরটি 1, এভাবে k − 1 পর্যন্ত। এর নাম coordinate compression — কনটেস্টের সবচেয়ে বেশি ব্যবহৃত কৌশলগুলোর একটি।

Pseudocode — coordinate compression (0-based)

vals = copy of a
sort(vals)
remove adjacent duplicates from vals       // k distinct values remain, sorted
for i = 0 .. n-1:
    c[i] = lower_bound(vals, a[i])         // index of a[i] inside vals, 0 .. k-1
// order is preserved:   a[i] < a[j]  <=>  c[i] < c[j]
// decode when needed:   a[i] == vals[c[i]]

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

int main() {
    vector<long long> a = {1000000000, 5, 42, 5, 999, 42, -7};
    vector<long long> vals = a;                               // copy, keep a intact
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end()); // sorted distinct values
    vector<int> c(a.size());
    for (size_t i = 0; i < a.size(); ++i)                     // value -> its index in vals
        c[i] = int(lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin());

    printf("distinct:");   for (long long x : vals) printf(" %lld", x);
    printf("\ncompressed:"); for (int x : c) printf(" %d", x);
    vector<int> cnt(vals.size(), 0);                          // small array instead of size 10^9
    for (int x : c) ++cnt[x];
    printf("\ncounts:");
    for (size_t k = 0; k < vals.size(); ++k) printf(" %lld:%d", vals[k], cnt[k]);
    printf("\nrestored:"); for (int x : c) printf(" %lld", vals[x]);
    printf("\n");
}

distinct: -7 5 42 999 1000000000
compressed: 4 1 2 1 3 2 0
counts: -7:1 5:2 42:2 999:1 1000000000:1
restored: 1000000000 5 42 5 999 42 -7

from bisect import bisect_left

a = [1000000000, 5, 42, 5, 999, 42, -7]
vals = sorted(set(a))                       # sorted distinct values
c = [bisect_left(vals, x) for x in a]       # value -> its index in vals
print("distinct:", *vals)
print("compressed:", *c)
cnt = [0] * len(vals)                       # small array instead of size 10^9
for x in c:
    cnt[x] += 1
print("counts:", *(f"{vals[k]}:{cnt[k]}" for k in range(len(vals))))
print("restored:", *(vals[x] for x in c))

distinct: -7 5 42 999 1000000000
compressed: 4 1 2 1 3 2 0
counts: -7:1 5:2 42:2 999:1 1000000000:1
restored: 1000000000 5 42 5 999 42 -7

কোথায় কাজে লাগে: Fenwick tree বা segment tree দিয়ে inversion গোনা (পর্ব ৩৪, ৩৬), বড় স্থানাঙ্কের আয়তক্ষেত্রের মোট ক্ষেত্রফল বের করা (sweep line), বা যেকোনো সমস্যা যেখানে মানের পরিসর বিশাল কিন্তু সংখ্যা কম। কনটেস্টে সমস্যার বিবরণে “a_i ≤ 10⁹” আর “n ≤ 2 × 10⁵” একসাথে দেখলেই এই কৌশলটির কথা মনে আনুন। একটি সতর্কতা: অনেক সময় query-তে আসা মানগুলোও (যা মূল array-তে নেই) আগে থেকেই vals-এ যোগ করতে হয় — সব প্রশ্ন আগে পড়ে নিয়ে তারপর compress করা (offline processing).

৮ · পুরোটা না সাজিয়ে — top-k, k-তম উপাদান আর সাজানো কি না যাচাই

১০ লাখ পরীক্ষার্থীর মধ্যে সেরা ১০০ জনের তালিকা চাই। পুরোটা সাজালে O(n log n) — প্রায় ২ কোটি তুলনা। কিন্তু বাকি ৯ লাখ ৯৯ হাজার ৯০০ জনের ক্রম আমাদের দরকারই নেই। এমন top-k প্রশ্নের জন্য তিনটি তৈরি হাতিয়ার আছে।

O(n log k) কেন: partial_sort প্রথম k টি উপাদান দিয়ে একটি max-heap বানায় (পর্ব ২৩)। তারপর বাকি প্রতিটি উপাদান heap-এর শিকড়ের (এ পর্যন্ত পাওয়া k টির মধ্যে সবচেয়ে বড়) সাথে তুলনা হয়; ছোট হলে শিকড় বাদ দিয়ে এটি ঢোকে — O(log k). n টি উপাদানে O(n log k), শেষে heap-টি সাজাতে O(k log k). k = 100, n = 10⁶ হলে log k ≈ 7, log n ≈ 20 — প্রায় তিন গুণ কম কাজ, আর জায়গা মাত্র O(k). স্রোতের মতো আসা ডেটায় (যেমন সার্ভারের লগ) এটিই একমাত্র উপায়, কারণ সব ডেটা একসাথে মেমরিতে রাখাই সম্ভব নয়।

nth_element: পর্ব ২২-এর quickselect — partition-এর পর শুধু যে দিকে k-তম উপাদান আছে সেই দিকে নামা। প্রতিবার গড়ে অর্ধেক বাদ পড়ে, তাই n + n/2 + n/4 + … ≈ 2n, গড়ে O(n). libstdc++ এখানেও introsort-এর মতো নিরাপত্তা রাখে (রিকার্শন বেশি গভীর হলে অন্য পদ্ধতিতে যায়)। কাজ শেষে k-তম ঘরে ঠিক সেই উপাদান থাকে যা পুরো সাজালে থাকত, আর তার বাঁয়ের সব উপাদান তার চেয়ে ছোট বা সমান, ডানের সব বড় বা সমান — কিন্তু দুই পাশের ভেতরে কোনো ক্রমের নিশ্চয়তা নেই।

vector<int> m = marks;                                   // keep the original
nth_element(m.begin(), m.begin() + m.size() / 2, m.end());
int median = m[m.size() / 2];                            // average O(n), not O(n log n)

partial_sort(m.begin(), m.begin() + 3, m.end(), greater<int>());   // top 3, high first

bool ok = is_sorted(v.begin(), v.end(), cmp);            // O(n): verify any sort result

is_sorted-কে তুচ্ছ মনে হলেও এটি যাচাইয়ের সবচেয়ে সস্তা হাতিয়ার: নিজের লেখা (বা AI-এর লেখা) যেকোনো sort-এর পরে একটি assert(is_sorted(...)) বসালে O(n) খরচে বড় ভুল ধরা পড়ে। Python-এ all(x <= y for x, y in zip(a, a[1:])), বা Python 3.10+-এ itertools.pairwise.

৯ · মডিউল ৩-এর সব sort এক টেবিলে — আর কোনটি কখন

পর্ব ২০ থেকে ২৪-এর সব sort, সাথে দুটি লাইব্রেরি sort. “Adaptive” মানে ইনপুট আংশিক সাজানো থাকলে উল্লেখযোগ্যভাবে দ্রুত চলে। n = উপাদানের সংখ্যা, k = key-এর পরিসর, d = অঙ্কের সংখ্যা, b = ভিত্তি (base).

* ছোট ভাগে আগে রিকার্শন আর বড় ভাগে লুপ দিলে stack O(log n) থাকে; সরলভাবে লিখলে worst case-এ O(n). ** ভেতরের প্রতিটি bucket stable sort দিয়ে সাজালে। আরেকটি মনে রাখার মতো তথ্য: তুলনা-ভিত্তিক যেকোনো sort-এর worst case Ω(n log n) — পর্ব ২৪-এর decision tree যুক্তি। Counting আর radix এই সীমা ভাঙে, কারণ তারা তুলনা করে না, key-কে সরাসরি index হিসেবে ব্যবহার করে — তাই key-কে ছোট পরিসরের পূর্ণসংখ্যা হতে হয়। আর Timsort-এর best case O(n) সীমাটি ভাঙে না: সীমাটি worst case-এর, আর পুরো সাজানো ইনপুট worst case নয়।

কোনটি বেছে নেবেন — প্রশ্নের পর প্রশ্ন

নতুন সমস্যায় নিচের প্রশ্নগুলো ক্রমানুসারে করুন। প্রথম যে প্রশ্নের উত্তর “হ্যাঁ”, সাধারণত সেখানেই আপনার উত্তর।

C++:    nth_element(b, b + n/2, e);   partial_sort(b, b + 10, e, greater<>());
Python: heapq.nlargest(10, marks)
সময়:   গড়ে O(n);  O(n log k)

C++:    stable_sort(v.begin(), v.end(), byAmount);
Python: tx.sort(key=lambda t: t.amount)     # always stable
সময়:   O(n log n), বাড়তি O(n)

counting sort: 101টি ঘরের count array
সময়:   Θ(n + k) = Θ(n),  k = 101
শর্ত:   key পূর্ণসংখ্যা, পরিসর ছোট (পর্ব ২৪)

Python/Java: Timsort নিজেই run চিনে নেয়
ছোট n (≤ 20 বা কাছাকাছি): insertion sort
সময়:   প্রায় O(n) — যত বেশি ক্রম, তত দ্রুত

C++:    make_heap(b, e);  sort_heap(b, e);
সময়:   সবসময় O(n log n), বাড়তি জায়গা O(1)
দাম:    cache-বান্ধব নয়, stable নয়

C++:    sort(v.begin(), v.end(), cmp);    // cmp: strict, never <=
Python: v.sort(key=...)
সময়:   O(n log n);  n = 10^6 হলে এক সেকেন্ডের অনেক কম

১০ · AI-এর যুগে সর্টিং — এক লাইনের কোডে লুকোনো ভুল

সর্টিংয়ের কোড প্রায়ই এক লাইন — sort(..., cmp). তাই AI-এর দেওয়া সমাধানে ভুলটিও লুকোয় ঠিক ওই এক লাইনের comparator বা key-এর ভেতরে: একটি <=, ভুল দিকে মাইনাস, টাই ভাঙার নিয়ম বাদ পড়া, বা stability ধরে নেওয়া যেখানে তা নেই। ছোট উদাহরণে উত্তর মিলে যায়, কারণ সেখানে টাই নেই বা উপাদান ১৬টির কম। আর complexity নিয়ে AI কখনো বলে “sort আছে, তাই O(n log n)” — অথচ comparator-এর ভেতরে string কপি বা O(n) কাজ থাকলে আসল খরচ আরও বেশি।

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

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

• Comparator-এ শুধু কঠোর তুলনা (<, >); !cmp(x, x) সব x-এ সত্য
• সমান key-এর ক্ষেত্রে ফল কী হবে জানি — stable sort ব্যবহার করেছি, অথবা সব টাই নিজে ভেঙেছি
• Edge case চালিয়েছি: খালি, এক উপাদান, সব সমান, আগেই সাজানো, উল্টো, ঋণাত্মক ও খুব বড় মান
• ফলের ওপর is_sorted (বা Python-এ জোড়ায় জোড়ায় যাচাই) বসিয়েছি
• ছোট এলোমেলো ইনপুটে brute force (যেমন সব জোড়া তুলনা করে rank) চালিয়ে হাজারবার উত্তর মিলিয়েছি
• Complexity-তে comparator বা key-এর নিজের খরচ ধরেছি (string তুলনা O(দৈর্ঘ্য))