এই পর্বে যা শিখবেন
- সাজানোর তিনটি মূল কৌশল — insertion, merge আর quicksort — ধাপে ধাপে চোখের সামনে
- কোন পদ্ধতি কখন দ্রুত, কখন ধীর, আর কতটুকু বাড়তি মেমরি লাগে
- Stable sort কেন মেধাতালিকার মতো একাধিক নিয়মে সাজানোর সময় জরুরি
- তুলনা করে সাজানোর গতির একটি গাণিতিক সীমা, আর counting sort কীভাবে তা এড়ায়
qsort-এর জন্য নির্ভুল comparator লেখা, আর AI-এর লেখা sorting কোড পরীক্ষা করার পদ্ধতি
১ · সাজানো কেন এত গুরুত্বপূর্ণ
HSC-র ফল প্রকাশের দিনটির কথা ভাবুন। বোর্ডের কম্পিউটারে কয়েক লাখ পরীক্ষার্থীর নম্বর জমা আছে, কিন্তু সেগুলো এলোমেলো — যে খাতা যখন দেখা হয়েছে, সেই ক্রমে। এখন দরকার মেধাতালিকা: সবচেয়ে বেশি নম্বর ওপরে, তারপর ক্রমে নিচে। এই কাজটিকেই বলে sorting — একটি নির্দিষ্ট নিয়মে (ছোট থেকে বড়, বড় থেকে ছোট, বর্ণানুক্রমে) ডেটা সাজানো।
শুনতে সাধারণ, কিন্তু কম্পিউটার বিজ্ঞানে sorting সবচেয়ে বেশি গবেষণা করা বিষয়গুলোর একটি। কারণ সাজানো ডেটায় অনেক কাজ প্রায় বিনা পরিশ্রমে হয়:
দ্রুত খোঁজা
অভিধানে শব্দ খুঁজতে আপনি মাঝখানে খুলে বোঝেন আগে না পরে। সাজানো তালিকায় এই কৌশলের নাম binary search — পরের পর্বের বিষয়।
১০ লাখে মাত্র ~২০ বার দেখাএকই জিনিস পাশাপাশি
সাজানোর পর একই মোবাইল নম্বর বা একই রোল দুবার থাকলে তারা পাশাপাশি চলে আসে। তখন একবার চোখ বুলিয়েই deduplication করা যায়।
ভোটার তালিকায় দুবার নামর্যাংকিং
মেধাতালিকা, ক্রিকেটের ব্যাটিং গড়ের তালিকা, অনলাইন দোকানে “দাম কম থেকে বেশি” — সবই sorting.
ভর্তি পরীক্ষার মেধাক্রমদলে ভাগ করা
জেলা অনুযায়ী সাজালে একই জেলার সবাই একসাথে আসে, তখন প্রতিটি জেলার গড় এক পাসেই বের হয়।
জেলাভিত্তিক ফলাফলএই পর্বের প্রশ্ন: সাজানো কতভাবে করা যায়, কোন পদ্ধতিতে কত কাজ, আর বাস্তবের সফটওয়্যার কোনটি বেছে নেয় কেন। আগের পর্বের time complexity এখানে সরাসরি কাজে লাগবে।
বেশিরভাগ sorting পদ্ধতি একটিমাত্র প্রশ্নই বারবার করে: “এই দুজনের মধ্যে কে আগে বসবে?” এমন পদ্ধতিকে বলে comparison sort. তাই কোনো পদ্ধতির খরচ মাপার সবচেয়ে সহজ উপায় — মোট কতবার তুলনা করতে হলো, তা গোনা।
Sorting কম্পিউটারের চেয়েও পুরোনো সমস্যা। পাঞ্চ কার্ডের যুগে আলাদা যন্ত্রই ছিল শুধু কার্ড সাজানোর জন্য। আর প্রথম দিকের কম্পিউটারের সময়ের একটা বড় অংশ খরচ হতো শুধু সাজাতে। ১৯৭৩ সালে Donald Knuth তাঁর বিখ্যাত বই The Art of Computer Programming-এর তৃতীয় খণ্ডের নাম দেন “Sorting and Searching” — পুরো একটি খণ্ড শুধু সাজানো আর খোঁজা নিয়ে। আজও এটি এই বিষয়ের সবচেয়ে মান্য বইগুলোর একটি।
২ · সহজ পদ্ধতি — হাতে তাস সাজানোর মতো
প্রথমে তিনটি সহজ পদ্ধতি দেখি। তিনটিই কয়েক লাইনে লেখা যায়, আর তিনটিই ছোট ডেটার জন্য যথেষ্ট ভালো।
| পদ্ধতি | মূল চিন্তা | বাস্তবের উদাহরণ |
|---|---|---|
| Selection sort | বাকিদের মধ্যে সবচেয়ে ছোটটি খুঁজে এনে সামনে বসানো, তারপর আবার একই কাজ | PT ক্লাসে সবচেয়ে খাটো জনকে বারবার খুঁজে লাইনের সামনে আনা |
| Bubble sort | পাশাপাশি দুজনকে তুলনা করা, উল্টো থাকলে জায়গা বদলানো; বড়রা বুদবুদের মতো শেষে ভেসে যায় | লাইনে পাশের জনের সাথে বারবার উচ্চতা মিলিয়ে জায়গা বদল |
| Insertion sort | সাজানো অংশে নতুন একটি উপাদান ঠিক জায়গায় ঢুকিয়ে দেওয়া | হাতে তাস তোলা — প্রতিটি নতুন তাস ঠিক জায়গায় গুঁজে দেওয়া |
তাস খেলার সময় আপনি কীভাবে কার্ড সাজান? একটি একটি করে তোলেন। হাতের কার্ডগুলো এর মধ্যেই সাজানো থাকে। নতুন কার্ডটি ডান থেকে বাঁয়ে মিলিয়ে দেখেন — যতক্ষণ হাতের কার্ড বড়, ততক্ষণ সেগুলো একটু সরিয়ে জায়গা করেন। ছোট কার্ড পেলেই থামেন, নতুনটি গুঁজে দেন। এটাই insertion sort — আপনি জীবনে বহুবার এটি করেছেন, শুধু নামটি জানতেন না।
নিচে পাঁচটি সংখ্যা insertion sort-এ সাজানো হচ্ছে। লাল দাগ দেওয়া ঘরটি দেখায় এই ধাপে কোন সংখ্যা জায়গা পেল। নিচের টেবিলে তুলনার হিসাব খেয়াল করুন।
| সাজানো অংশ | |
| নতুন তোলা তাস | |
| এই ধাপে তুলনা | |
| মোট তুলনা |
- শুরু। অ্যারেতে আছে 5, 2, 4, 1, 3. প্রথম সংখ্যা 5-কে একাই একটি “সাজানো হাত” ধরা হলো — একটি তাস তো সবসময়ই সাজানো।
- 2 তোলা হলো। তুলনা: 5 কি 2-এর চেয়ে বড়? হ্যাঁ — তাই 5 এক ঘর ডানে সরল। বাঁয়ে আর কেউ নেই, তাই 2 বসল একদম শুরুতে। মাত্র ১টি তুলনা।
- 4 তোলা হলো। 5 বড়, তাই সরল। তারপর 2 — সে 4-এর চেয়ে ছোট, তাই থামা। 4 বসল 2 আর 5-এর মাঝে। ২টি তুলনা।
- 1 তোলা হলো। 5, 4, 2 — তিনজনই বড়, তিনজনই এক ঘর করে সরল। 1 গিয়ে বসল একদম সামনে। ছোট সংখ্যা পেছনে থাকলে কাজ বেশি, এটাই তার প্রমাণ।
- 3 তোলা হলো। 5 আর 4 সরল, 2-এর কাছে এসে থামা। 3 বসল 2 আর 4-এর মাঝে। অ্যারে সাজানো হয়ে গেল।
- হিসাব মেলান। মোট ৯টি তুলনা। পুরো উল্টো ক্রমে লাগত ১০টি, আর আগে থেকে সাজানো থাকলে মাত্র ৪টি — প্রতিটি নতুন তাস একবার দেখেই থেমে যেত। এই পার্থক্যই insertion sort-এর আসল চরিত্র।
সবচেয়ে খারাপ অবস্থায় n-টি উপাদানে মোট তুলনা হয় ১ + ২ + … + (n−১), মানে প্রায় n²/২. তাই এই তিন সহজ পদ্ধতির কাজ বাড়ে n²-এর হারে. ১,০০০টি সংখ্যায় প্রায় ৫ লাখ তুলনা, আর ১০ লাখ সংখ্যায় প্রায় ৫০,০০০ কোটি! তবে insertion sort-এর একটি বিশেষ গুণ আছে: ডেটা প্রায় সাজানো হলে প্রতিটি নতুন উপাদান মাত্র এক-দুই ঘর সরে, তাই কাজ প্রায় n-এর সমান। নিচের প্রোগ্রামে এটি নিজে মেপে দেখুন:
#include <stdio.h>
#include <stdlib.h>
#define N 1000
long cmp = 0; /* comparison counter */
int greater(int x, int y) { cmp++; return x > y; }
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1; /* pick up a new card */
while (j >= 0 && greater(a[j], key)) { a[j + 1] = a[j]; j--; }
a[j + 1] = key; /* drop it in its place */
}
}
int main(void) {
static int s[N], r[N], x[N];
for (int i = 0; i < N; i++) { s[i] = i; r[i] = N - i; x[i] = rand() % N; }
insertion_sort(s, N); printf("sorted : %ld\n", cmp); cmp = 0;
insertion_sort(r, N); printf("reverse: %ld\n", cmp); cmp = 0;
insertion_sort(x, N); printf("random : %ld\n", cmp);
return 0;
}তিনটি অ্যারে, প্রতিটিতে ১,০০০টি সংখ্যা: একটি আগে থেকেই সাজানো, একটি পুরো উল্টো, আর একটি এলোমেলো। ফল দেখুন — সাজানোটিতে মাত্র 999টি তুলনা, উল্টোটিতে 499500টি (ঠিক n(n−১)/২), আর এলোমেলোটিতে মোটামুটি তার অর্ধেক। একই কোড, একই n, অথচ কাজের পার্থক্য ৫০০ গুণ! প্রতিটি তুলনা হচ্ছে greater ফাংশনের ভেতর দিয়ে, তাই গোনা সহজ — অংশ ৭-এর comparator-ও ঠিক এমন একটি “তুলনার ফাংশন”. আরেকটি সূক্ষ্ম বিষয়: greater শুধু কঠোরভাবে বড় হলে সত্য, তাই সমান মান কখনো একে অপরকে টপকায় না — অংশ ৫-এ এটি খুব কাজে লাগবে।
Selection sort সাজানো ডেটাতেও পুরো বাকি অংশ খোঁজে, তাই আগে থামতে পারে না। Bubble sort বইয়ে থাকে, বাস্তবে প্রায় নেই। ছোট ডেটায় পেশাদারদের পছন্দ insertion sort — বড় library-ও ভেতরে ছোট টুকরোর জন্য এটিই ডাকে।
৩ · Merge sort — ভাগ করুন, তারপর জোড়া লাগান
n² যদি খুব ধীর হয়, তবে দ্রুত হওয়ার উপায় কী? উত্তর আসে divide and conquer থেকে। Merge sort-এর চিন্তা তিন লাইনের:
- অ্যারেকে দুই সমান ভাগে ভাগ করুন।
- প্রতিটি ভাগকে একই নিয়মে আলাদাভাবে সাজান (recursion). একটিমাত্র উপাদান থাকলে সেটি তো এমনিতেই সাজানো।
- সাজানো দুটি ভাগকে জোড়া লাগিয়ে একটি সাজানো অ্যারে বানান — একে বলে merge.
ব্যাংকের একটি কাউন্টারের সামনে দুটি লাইন। প্রতিটি লাইন টোকেন নম্বর অনুযায়ী আগে থেকেই সাজানো। কাউন্টারের ক্যাশিয়ার শুধু দুই লাইনের সামনের দুজনের টোকেন দেখেন — যার নম্বর ছোট, তিনি আগে আসেন। পেছনের কাউকে দেখার দরকারই নেই! প্রতিটি তুলনায় একজন করে কাজ শেষ, তাই দুই লাইনে মোট n জন থাকলে প্রায় n তুলনাতেই সবাই একটি সাজানো লাইনে চলে আসেন। Merge ঠিক এই কাজ।
নিচে আটজন শিক্ষার্থীর নম্বর merge sort-এ সাজানো হচ্ছে। প্রথম চার ধাপে শুধু ভাগ, পরের তিন ধাপে জোড়া লাগানো:
- শুরু। আটটি নম্বর এলোমেলো: 62, 45, 88, 30, 71, 55, 90, 40. সরাসরি সাজাতে না গিয়ে আমরা আগে কাজটিকে ছোট করব।
- প্রথম ভাগ। আটটিকে চারটি-চারটি করে দুই ভাগ। শুধু মাঝখান দিয়ে কাটা — কোনো তুলনাই লাগে না।
- আবার ভাগ। প্রতিটি চারের দল ভেঙে দুইয়ের দল হলো। একই নিয়ম, ছোট সমস্যা — এটাই recursion.
- একক উপাদান। এবার প্রতিটি দলে একটি করে সংখ্যা। একটি সংখ্যা নিজেই সাজানো, তাই ভাগ করা এখানেই থামল (এটি recursion-এর base case). হলুদ ঘরগুলো এখন আটটি ছোট “সাজানো তালিকা”.
- জোড়ায় merge. পাশাপাশি দুটি একক তালিকা জোড়া লাগল: 62 আর 45 থেকে [45 62], 88 আর 30 থেকে [30 88] — প্রতিটিতে মাত্র ১টি তুলনা। মোট ৪টি তুলনা।
- চারের দলে merge. [45 62] আর [30 88]: সামনের দুজন 45 আর 30 — 30 ছোট, সে আগে। তারপর 45, তারপর 62, শেষে 88. ফল [30 45 62 88]. অন্য দিকে একইভাবে [40 55 71 90].
- শেষ merge — ব্যাংকের দুই লাইন। 30 বনাম 40 → 30. 45 বনাম 40 → 40. 45 বনাম 55 → 45. 62 বনাম 55 → 55. 62 বনাম 71 → 62. 88 বনাম 71 → 71. 88 বনাম 90 → 88. শেষে 90 একা। ৭টি তুলনায় আটজন সাজানো!
- খরচের হিসাব। জোড়া লাগানোর স্তর ৩টি, কারণ ৮-কে অর্ধেক করতে করতে ১-এ আনতে ৩ বার লাগে (log₂ 8 = 3). প্রতিটি স্তরে কাজ মোটামুটি n, তাই মোট প্রায় n × log n. ১০ লাখ সংখ্যায় স্তর মাত্র ২০টি — মোট প্রায় ২ কোটি তুলনা।
প্রায় ৫০,০০০ কোটি তুলনা বনাম প্রায় ২ কোটি তুলনা
Merge sort-এর সবচেয়ে বড় গুণ — ডেটা এলোমেলো, উল্টো বা সাজানো যেমনই হোক, কাজ সবসময় প্রায় n log n. অর্থাৎ তার worst case-ও ভালো। দাম একটাই: merge-এর ফল রাখতে আরও n ঘরের একটি বাড়তি অ্যারে লাগে — যেন কাউন্টারের পাশে তৃতীয় একটি লাইন। ছোট মেমরির যন্ত্রে এটি বড় সমস্যা।
Merge sort-এর ধারণা দেন গণিতবিদ John von Neumann, ১৯৪৫ সালে — তখনো আধুনিক অর্থে প্রোগ্রাম রাখা যায় এমন কম্পিউটার সবে তৈরি হচ্ছে। প্রায় আশি বছর পরেও এটি ব্যবহৃত হচ্ছে, বিশেষ করে যখন ডেটা মেমরিতে আঁটে না (ভাবনার প্রশ্ন ০৩ দেখুন)।
৪ · Quicksort — একজনকে মাপকাঠি ধরে দুই দলে ভাগ
Merge sort আগে ভাগ করে, পরে খেটে জোড়া লাগায়। Quicksort করে উল্টোটা — ভাগ করার সময়েই খাটে, তাই পরে জোড়া লাগানোর কিছু থাকে না।
স্কুলের মাঠে PT শিক্ষক পুরো ক্লাসকে উচ্চতা অনুযায়ী দাঁড় করাতে চান। তিনি একজনকে বেছে নিলেন — ধরুন রাফি — আর বললেন, “রাফির চেয়ে খাটোরা বাঁ দিকে, লম্বারা ডান দিকে।” এক ডাকেই ক্লাস দুই দলে ভাগ, আর রাফি দাঁড়িয়ে গেল ঠিক তার চূড়ান্ত জায়গায়। এবার শিক্ষক প্রতিটি দলের ভেতরে একই কাজ আবার করবেন। রাফির ভূমিকা যে নেয়, তাকে বলে pivot, আর দুই দলে ভাগ করার কাজটির নাম partition.
নিচের ডায়াগ্রামে সাতটি সংখ্যার partition দেখুন। Pivot হলো শেষ সংখ্যা, 5. বাঁ থেকে একে একে প্রতিটি সংখ্যা দেখা হয়; 5-এর চেয়ে ছোট পেলে তাকে “ছোটদের এলাকায়” পাঠানো হয়। ওপরের সারিতে ঘরের নম্বর, লাল দাগ মানে এই ধাপে যে ঘরগুলো দেখা বা বদলানো হলো।
| যে ঘর দেখা হচ্ছে | |
| সিদ্ধান্ত | |
| ছোটদের এলাকা |
- Pivot বেছে নেওয়া। অ্যারে: 7, 2, 9, 4, 3, 8, 5. শেষ ঘরের 5-কে pivot ধরা হলো (হলুদ)। লক্ষ্য: 5-এর চেয়ে ছোট সবাই বাঁয়ে, বড় সবাই ডানে। এখনো “ছোটদের এলাকা” খালি।
- ঘর [0] = 7. 7 কি 5-এর চেয়ে ছোট? না। তাই সে যেখানে আছে সেখানেই থাকুক — কোনো অদলবদল নেই।
- ঘর [1] = 2. 2 ছোট! তাকে ছোটদের এলাকার পরের ঘরে, মানে [0]-এ পাঠানো হলো। সেখানে থাকা 7-এর সাথে জায়গা বদল। এখন ছোটদের এলাকা = [0].
- ঘর [2] = 9. বড়, থাকুক।
- ঘর [3] = 4. ছোট! ঘর [1]-এর 7-এর সাথে জায়গা বদল। খেয়াল করুন, 7 বারবার ডানে ঠেলা খাচ্ছে — বড়রা এভাবেই ডানে জমা হয়।
- ঘর [4] = 3. ছোট! [2]-এর 9-এর সাথে বদল। এখন [0..2] পুরোটাই ছোটদের এলাকা: 2, 4, 3.
- ঘর [5] = 8. বড়, থাকুক। সবাইকে দেখা শেষ — মোট ৬টি তুলনা, অর্থাৎ partition-এর খরচ প্রায় n.
- Pivot নিজের জায়গায়। ছোটদের এলাকার পরের ঘর [3]-এ pivot 5 বসল, সেখানকার 7 গেল শেষে। এখন বাঁয়ে সবাই ছোট (2, 4, 3), ডানে সবাই বড় (9, 8, 7). 5 আর কোনোদিন নড়বে না।
- দুই দল আলাদা করে। এবার বাঁয়ের [2 4 3] আর ডানের [9 8 7] — প্রত্যেকের ভেতরে আবার একই কাজ (recursion). কোনো merge লাগে না, কারণ বাঁয়ের সবাই আগে থেকেই ডানের সবার চেয়ে ছোট। ফল: 2, 3, 4, 5, 7, 8, 9.
Quicksort-এর দুটি বড় গুণ। এক, এটি in-place — শুধু অ্যারের ভেতরেই জায়গা বদল, merge sort-এর মতো বাড়তি n ঘর লাগে না। দুই, পাশাপাশি ঘর একে একে পড়ে বলে CPU cache খুব ভালোভাবে কাজে লাগে। তাই বাস্তবে এটি প্রায়ই merge sort-এর চেয়েও দ্রুত চলে। এলোমেলো ডেটায় pivot সাধারণত মোটামুটি মাঝামাঝি পড়ে, ফলে দুই দল প্রায় সমান হয় — তাই average case-এ কাজ n log n.
কিন্তু খারাপ pivot বিপদ ডাকে। ধরুন অ্যারে আগে থেকেই সাজানো: 1, 2, 3, …, n. আর আপনি সবসময় শেষ সংখ্যাকে pivot ধরেন। তাহলে pivot প্রতিবারই সবচেয়ে বড় — ডানের দল খালি, বাঁয়ের দলে বাকি সবাই। প্রতিটি ধাপে মাত্র একজন কমে। মোট কাজ n + (n−১) + … + ১ ≈ n²/২ — ঠিক সেই ধীর পদ্ধতিগুলোর মতো! আর recursion n স্তর গভীরে যায়, বড় n-এ stack overflow হতে পারে। অথচ “আগে থেকেই সাজানো ডেটা আবার সাজানো” বাস্তবে খুব সাধারণ ঘটনা।
সমাধান হলো pivot বুদ্ধি করে বাছা: এলোমেলো একটি ঘর থেকে pivot নেওয়া, অথবা প্রথম, মাঝের ও শেষের তিনটির মাঝের মানটি নেওয়া (median-of-three). তবু কেউ ইচ্ছে করে বিশেষ ইনপুট বানালে n² সম্ভব — তাই বাস্তবের library বাড়তি সুরক্ষা রাখে (অংশ ৮)।
Quicksort উদ্ভাবন করেন ব্রিটিশ কম্পিউটার বিজ্ঞানী Tony Hoare, ১৯৫৯ সালে, যখন তিনি মস্কো স্টেট ইউনিভার্সিটিতে ছাত্র হিসেবে যন্ত্রের সাহায্যে অনুবাদের একটি প্রকল্পে কাজ করছিলেন — শব্দের তালিকা দ্রুত সাজানোর দরকার ছিল। ১৯৬১-৬২ সালে তিনি এটি প্রকাশ করেন। পরে তিনি Turing Award পান। C-এর qsort নামটিও এসেছে quicksort থেকেই।
৫ · Stability — সমান নম্বর পেলে কে আগে?
এবার একটি সূক্ষ্ম কিন্তু খুব বাস্তব প্রশ্ন। কলেজের একটি তালিকা আগে থেকেই রোল অনুযায়ী সাজানো। এখন নম্বর অনুযায়ী (বেশি নম্বর আগে) সাজাতে হবে। দুজনের নম্বর সমান হলে কী হবে? স্বাভাবিক প্রত্যাশা — যার রোল আগে, সে আগে থাকবে, ঠিক আগের তালিকার মতো।
যে sorting পদ্ধতি এই প্রত্যাশা সবসময় রাখে — সমান মানের উপাদানগুলোর আগের পারস্পরিক ক্রম বদলায় না — তাকে বলে stable sort. নিচে একই তালিকা দুই ধরনের sorting-এ দেখুন:
| ১ম | |
| ২য় | |
| ৩য় | |
| ৪র্থ | |
| ৫ম |
- শুরুর তালিকা — রোল অনুযায়ী। পাঁচজন: Anik (৮৫), Bithi (৯২), Chayan (৮৫), Dipa (৭৮), Emon (৯২). দুই জোড়ার নম্বর সমান — Bithi ও Emon (৯২), Anik ও Chayan (৮৫).
- Stable sort, নম্বর অনুযায়ী। Bithi (রোল ০২) আছে Emon (রোল ০৫)-এর আগে, Anik (০১) আছে Chayan (০৩)-এর আগে — ঠিক আগের তালিকার মতো। কেউ আলাদা করে রোলের কথা বলেনি, তবু রোলের ক্রম রয়ে গেছে। এটাই stability.
- Unstable sort, নম্বর অনুযায়ী। নম্বরের হিসাবে এটিও “সঠিক” — ৯২, ৯২, ৮৫, ৮৫, ৭৮. কিন্তু Emon চলে এসেছে Bithi-র আগে, Chayan এসেছে Anik-এর আগে (রঙিন সারিগুলো বদলেছে)। পদ্ধতিটি ভুল করেনি — সমানদের ক্রম রাখার প্রতিশ্রুতিই দেয়নি।
- নিরাপদ সমাধান — নিয়মেই দুটি চাবি। “আগে নম্বর (বেশি আগে), নম্বর সমান হলে রোল (ছোট আগে)” — এই পূর্ণ নিয়মটি comparator-এ লিখে দিলে কোনো দুজন আর “সমান” থাকে না, তাই stable হোক বা না হোক, ফল সবসময় একই। qsort ব্যবহার করলে এটাই একমাত্র নির্ভরযোগ্য পথ।
মনে রাখার কৌশল: যে পদ্ধতি শুধু পাশাপাশি উপাদান সরায় আর সমান হলে টপকায় না, সে সাধারণত stable. যে পদ্ধতি দূরের দুটি ঘরে লাফ দিয়ে জায়গা বদলায়, সে সাধারণত নয় — লাফের সময় মাঝের সমান কাউকে টপকে যেতে পারে।
| পদ্ধতি | Stable? | কারণ |
|---|---|---|
| Insertion sort | হ্যাঁ | শুধু বড় হলে সরায়, সমান পেলে থেমে যায় — টপকায় না |
| Bubble sort | হ্যাঁ | শুধু পাশাপাশি, আর শুধু কঠোরভাবে বড় হলে বদলায় |
| Merge sort | হ্যাঁ | সমান হলে বাঁয়ের লাইন থেকে আগে নেওয়া হয় — এই নিয়ম মানলে |
| Selection sort | না | সবচেয়ে ছোটটিকে সামনে আনতে দূরের ঘরে লাফ দিয়ে বদল |
| Quicksort | না | partition-এ দূরের ঘরের সাথে বদল (ওপরে 7-এর যাত্রা দেখুন) |
| C-এর qsort | নিশ্চয়তা নেই | C standard ভেতরের পদ্ধতিই ঠিক করে দেয়নি |
Stability-র আসল শক্তি একাধিক চাবিতে সাজানোয়। Stable sort থাকলে কৌশলটি হলো কম গুরুত্বের চাবি দিয়ে আগে, বেশি গুরুত্বের চাবি দিয়ে পরে সাজানো। আগে রোল দিয়ে, পরে নম্বর দিয়ে — ফল: নম্বর অনুযায়ী তালিকা, সমান নম্বরে রোলের ক্রম। Spreadsheet-এ একটার পর একটা কলামে ক্লিক করে সাজানো ঠিক এভাবেই কাজ করে।
৬ · n log n-এর দেয়াল, আর counting sort-এর ফাঁক
এত পদ্ধতি দেখার পর স্বাভাবিক প্রশ্ন: আরও চালাক কোনো পদ্ধতি কি n log n-এর চেয়েও দ্রুত সাজাতে পারবে? উত্তরটি বিস্ময়কর — যদি শুধু তুলনা করে সাজাতে হয়, তবে না। এটি কোনো প্রোগ্রামারের ব্যর্থতা নয়; এটি গণিতের প্রমাণিত সীমা, যাকে বলে sorting lower bound.
যুক্তিটি “বিশ প্রশ্ন” খেলার মতো। n-টি আলাদা সংখ্যা মোট n! (n ফ্যাক্টোরিয়াল) রকম ক্রমে সাজানো থাকতে পারে। তিনটি হলে ৩ × ২ × ১ = ৬ রকম। পদ্ধতিটিকে বুঝে নিতে হবে আসলে এই ৬টির কোনটি সামনে আছে — তবেই সে সঠিকভাবে সাজাতে পারবে। কিন্তু প্রতিটি তুলনার উত্তর শুধু “হ্যাঁ” বা “না”, তাই একটি তুলনা সম্ভাবনাগুলোকে বড়জোর অর্ধেক করতে পারে। ৬টি সম্ভাবনাকে ১-এ নামাতে অর্ধেক করতে হয় অন্তত ৩ বার (৬ → ৩ → ২ → ১)।
| উপাদান (n) | সম্ভাব্য ক্রম (n!) | সবচেয়ে খারাপ ইনপুটে অন্তত যত তুলনা লাগবেই |
|---|---|---|
| ৩ | ৬ | ৩ |
| ৫ | ১২০ | ৭ (কারণ ২⁶ = ৬৪, যথেষ্ট নয়; ২⁷ = ১২৮) |
| ১০ | ৩৬,২৮,৮০০ | ২২ |
| বড় n | বিশাল | মোটামুটি n × log₂ n |
গণিতে দেখানো যায় log₂(n!) প্রায় n log₂ n-এর সমান। তাই merge sort আসলে প্রায় সর্বোত্তম — তুলনার খেলায় এর চেয়ে বেশি দূর যাওয়া সম্ভব নয়।
দেয়ালের ফাঁক: তুলনাই না করা
কিন্তু শর্তটি খেয়াল করুন — “শুধু তুলনা করে”. যদি মানগুলো সম্পর্কে আগে থেকে কিছু জানা থাকে, তবে তুলনা ছাড়াই সাজানো যায়। পরীক্ষার নম্বর হলো সবচেয়ে ভালো উদাহরণ: কয়েক লাখ পরীক্ষার্থী, কিন্তু নম্বর শুধু ০ থেকে ১০০ — মাত্র ১০১ রকম মান।
ডাকঘরে চিঠি সাজানোর কথা ভাবুন। কর্মী দুটি চিঠি হাতে নিয়ে তুলনা করেন না। দেয়ালে প্রতিটি এলাকার জন্য একটি খোপ — চিঠির ঠিকানা দেখে সরাসরি সেই খোপে ফেলে দেন। শেষে খোপগুলো ক্রমে খালি করলেই সাজানো! Counting sort ঠিক এভাবে কাজ করে: ১০১টি খোপের একটি অ্যারে, প্রতিটি নম্বর দেখে সেই খোপের গণনা এক বাড়ানো, তারপর ০ থেকে ১০০ পর্যন্ত খোপগুলো পড়ে ফল লেখা।
Counting sort — খোপে গোনা
Marks 3, 1, 4, 1, 5, 3, 3 (range 0–5) → count each value, then read the boxes in order
খরচ: প্রতিটি নম্বর একবার দেখা (n), আর প্রতিটি খোপ একবার পড়া (k, মানে সম্ভাব্য মানের সংখ্যা) — মোট n + k. কয়েক লাখ পরীক্ষার্থী আর ১০১টি খোপে কাজ প্রায় n — n log n-এর চেয়েও কম! শুধু নম্বর নয়, পুরো রেকর্ড সাজাতে চাইলে খোপের গণনা থেকে প্রতিটি নম্বরের শুরুর ঘর হিসাব করে নেওয়া হয়; সেভাবে লিখলে counting sort stable-ও হয়।
Counting sort কোনো জাদু নয়। মানের পরিসর বড় হলে (যেমন যেকোনো int, প্রায় ৪০০ কোটি রকম মান) খোপের অ্যারেই মেমরিতে আঁটবে না। এটি বিশেষ পরিস্থিতির হাতিয়ার: অনেক ডেটা, কিন্তু অল্প রকম মান।
৭ · C-তে বাস্তবে — qsort আর নির্ভুল comparator
বাস্তব কাজে আপনি নিজে quicksort বা merge sort লিখবেন খুব কম। C-এর standard library-তে আছে qsort, যার কথা পর্ব ২৮-এ function pointer শেখার সময় দেখেছেন। মনে করিয়ে দিই: qsort জানে কীভাবে সাজাতে হয়, কিন্তু “দুজনের মধ্যে কে আগে” — সেই নিয়মটি আপনি একটি comparator ফাংশন হিসেবে দেন। comparator ঋণাত্মক ফেরত দিলে প্রথমজন আগে, ধনাত্মক দিলে পরে, শূন্য দিলে দুজন সমান।
সবচেয়ে প্রচলিত ভুল: return a - b;
অনেক টিউটোরিয়াল আর AI এই comparator দেয়, কারণ এটি ছোট ও দেখতে চতুর:
int cmp(const void *pa, const void *pb) {
return *(const int *)pa - *(const int *)pb; /* looks fine, hides an overflow */
}ছোট সংখ্যায় এটি ঠিকঠাক চলে — ৮৫ − ৯২ = −৭, ঋণাত্মক, তাই ৮৫ আগে। কিন্তু বড় সংখ্যায় বিপদ। ধরুন a = 2000000000 আর b = −2000000000. আসল বিয়োগফল ৪০০ কোটি, যা int-এ (সর্বোচ্চ প্রায় ২১৪ কোটি) আঁটে না। এটি overflow — C-তে undefined behavior. বেশিরভাগ মেশিনে ফল ঘুরে গিয়ে হয় −294967296, অর্থাৎ ঋণাত্মক — qsort ধরে নেয় ২০০ কোটি ছোট, −২০০ কোটি বড়! আর comparator একবার ভুল বললে পুরো অ্যারের ক্রম গোলমাল হয়ে যেতে পারে।
বিয়োগ নয়, দুটি তুলনা: return (a > b) - (a < b); প্রতিটি তুলনা ০ বা ১ দেয়, তাই ফল সবসময় −১, ০ বা ১ — overflow-এর কোনো সুযোগ নেই। বড় থেকে ছোট চাইলে দুই পাশ অদলবদল করুন: (a < b) - (a > b).
এবার একটি পূর্ণ উদাহরণ — মেধাতালিকা: নম্বর বেশি আগে, নম্বর সমান হলে নামের বর্ণানুক্রমে। পুরো নিয়মটি comparator-এ লেখা, তাই qsort stable না হলেও ফল নির্দিষ্ট:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct { char name[12]; int marks; } Student;
int by_marks_then_name(const void *pa, const void *pb) {
const Student *a = pa, *b = pb;
if (a->marks != b->marks) /* key 1: higher marks first */
return (a->marks < b->marks) - (a->marks > b->marks);
return strcmp(a->name, b->name); /* key 2: name A to Z */
}
int main(void) {
Student s[] = {{"Rafi", 78}, {"Mitu", 91}, {"Anik", 78}, {"Tania", 85}, {"Joy", 91}};
size_t n = sizeof s / sizeof s[0];
qsort(s, n, sizeof s[0], by_marks_then_name);
for (size_t i = 0; i < n; i++)
printf("%zu. %-6s %d\n", i + 1, s[i].name, s[i].marks);
return 0;
}ফল: Joy 91, Mitu 91, Tania 85, Anik 78, Rafi 78. প্রথম চাবি নম্বর — (a < b) - (a > b) লেখায় বেশি নম্বর আগে আসে। নম্বর আলাদা হলে সেখানেই উত্তর শেষ। সমান হলে দ্বিতীয় চাবি — strcmp নিজেই ঋণাত্মক, শূন্য বা ধনাত্মক দেয়, তাই সরাসরি ফেরত দেওয়া যায়। এই ধাঁচটি যেকোনো সংখ্যক চাবিতে বাড়ানো যায়: “প্রথম চাবি আলাদা হলে তার উত্তরই চূড়ান্ত, না হলে পরের চাবিতে যাওয়া।” একে বলে tie-breaker নিয়ম।
qsort-এর ভেতরে কোন পদ্ধতি চলে, C standard তা বলে দেয়নি — এটি library-র লেখকের সিদ্ধান্ত। নামে “q” থাকলেও ভেতরে quicksort থাকতেই হবে এমন নয়। Standard গতির কোনো নিশ্চয়তাও দেয় না, stable হওয়ারও না। তাই qsort-এর ওপর শুধু একটি ভরসাই করা যায়: comparator যে নিয়ম বলে, ফল সেই নিয়মে সাজানো হবে — বাকি সব নিয়ম আপনাকেই comparator-এ লিখে দিতে হবে।
৮ · বাস্তবের library — একাধিক পদ্ধতির মিশ্রণ
প্রথমে সব পদ্ধতি একসাথে মিলিয়ে নিন:
| পদ্ধতি | সবচেয়ে ভালো | গড় | সবচেয়ে খারাপ | বাড়তি জায়গা | Stable |
|---|---|---|---|---|---|
| Insertion | n (প্রায়-সাজানো) | n² | n² | প্রায় শূন্য | হ্যাঁ |
| Selection | n² | n² | n² | প্রায় শূন্য | না |
| Merge | n log n | n log n | n log n | n | হ্যাঁ |
| Quicksort | n log n | n log n | n² (খারাপ pivot) | log n (recursion) | না |
| Heapsort | n log n | n log n | n log n | প্রায় শূন্য | না |
| Counting | n + k | n + k | n + k | k (+ n) | হ্যাঁ (ঠিকভাবে লিখলে) |
কোনো একটিও সব ঘরে সেরা নয়। তাই বাস্তবের library-গুলো একটি নয়, কয়েকটি পদ্ধতি মিলিয়ে বানানো — একে বলে hybrid algorithm. দুটি বিখ্যাত উদাহরণ:
🛡️ Introsort
Introsort চলে quicksort দিয়ে। কিন্তু সে নিজের recursion কত গভীরে গেল, তা নজরে রাখে। খুব গভীরে চলে গেলে (মানে pivot বারবার খারাপ পড়ছে) সে heapsort-এ বদলে যায়, যার worst case-ও n log n. আর টুকরো খুব ছোট হলে (প্রায় ১৬টির কম) insertion sort ডাকে। ১৯৯৭ সালে David Musser এটি প্রকাশ করেন।
C++-এর std::sort (যেমন GCC-র library-তে)🧩 Timsort
Timsort বাস্তবের ডেটার একটি সত্য কাজে লাগায়: ডেটা প্রায়ই পুরো এলোমেলো নয়, ভেতরে আগে থেকেই সাজানো লম্বা টুকরো থাকে। সে এই টুকরোগুলো খুঁজে বের করে, ছোট টুকরো insertion sort দিয়ে বড় করে, তারপর merge sort-এর মতো জোড়া লাগায়। Stable. ২০০২ সালে Tim Peters Python-এর জন্য এটি লেখেন।
Python, Java (object-এর অ্যারে), Androidদুটির পেছনের চিন্তাই এই পর্বের সবচেয়ে বড় প্রকৌশল শিক্ষা: যেখানে যে পদ্ধতি সবচেয়ে ভালো, সেখানে সেটি ব্যবহার করুন, আর সবচেয়ে খারাপ অবস্থার জন্য সুরক্ষা রাখুন। “ধীর” insertion sort-ও তাই প্রায় সব hybrid-এর ভেতরে আছে।
qsort — ভেতরের পদ্ধতি library অনুযায়ী আলাদা। stable হওয়ার নিশ্চয়তা নেই। Stability দরকার হলে হয় comparator-এ tie-breaker দিন (যেমন আসল ঘরের নম্বর একটি বাড়তি member-এ রেখে), নয়তো নিজে merge sort লিখুন।
std::sort — দ্রুত, stable নয়, সাধারণত introsort. Stable দরকার হলে আলাদা ফাংশন std::stable_sort.
list.sort() ও sorted() — Timsort, সবসময় stable. তাই Python-এ “আগে রোলে, পরে নম্বরে” সাজানোর কৌশলটি নিশ্চিন্তে চলে।
সংখ্যার অ্যারেতে quicksort-ভিত্তিক পদ্ধতি; object-এর অ্যারেতে stable Timsort, কারণ সেখানেই একাধিক চাবিতে সাজানো বেশি লাগে।
৯ · AI-এর যুগে sorting — comparator যাচাই ও পরীক্ষা
“এই struct-এর অ্যারে নম্বর অনুযায়ী সাজাও” — AI কয়েক সেকেন্ডে লিখে দেয়, ছোট উদাহরণে ঠিক ফলও আসে। বিপদ এখানেই: sorting-এর ভুল সাধারণ ইনপুটে চুপ থাকে, ধরা পড়ে শুধু বড় সংখ্যা, সমান মান বা বিশেষ ক্রমে।
AI-এর লেখা sorting কোডে যে ভুলগুলো বারবার দেখা যায়
| AI যা লেখে | সমস্যা | কখন ধরা পড়ে |
|---|---|---|
return a - b; | বড় বা ঋণাত্মক মানে overflow, উল্টো উত্তর | খুব বড় সংখ্যায়, প্রায়ই production-এ গিয়ে |
return a->gpa - b->gpa; (double) | int-এ ফেরত দেওয়ার সময় 0.25 হয়ে যায় 0 — “সমান”! কোনো warning-ও আসে না | যখন পার্থক্য ১-এর কম — মানে প্রায় সবসময় |
return a > b; | শুধু ০ বা ১ দেয়, কখনো ঋণাত্মক নয় — নিয়মটি অসংগত | কিছু library-তে, কিছু ইনপুটে — অনিয়মিতভাবে |
| সমান মানের ক্রম “এমনিতেই থাকবে” ধরে নেওয়া | qsort stable নয় | অন্য compiler বা library-তে চালালে |
| নিজের লেখা quicksort, সবসময় শেষ ঘর pivot | সাজানো ডেটায় n², গভীর recursion | বড় ও আগে থেকে সাজানো ইনপুটে |
তৃতীয় সারিটি সবচেয়ে সূক্ষ্ম। Comparator-কে একটি সংগত নিয়ম মানতে হয়: a আগে b, আর b আগে c হলে a অবশ্যই c-এর আগে; আর cmp(a, b) ঋণাত্মক হলে cmp(b, a) ধনাত্মক হতেই হবে। নিয়ম ভাঙলে ফল শুধু ভুল ক্রম নয় — ২০২৪ সালে নিরাপত্তা গবেষকরা দেখান, Linux-এর বহুল ব্যবহৃত C library (glibc)-এর qsort-এ এমন অসংগত comparator দিলে, বিশেষ পরিস্থিতিতে, অ্যারের সীমার বাইরে মেমরিতে লেখা পর্যন্ত হতে পারত।
Sorting কোড পরীক্ষার সবচেয়ে শক্তিশালী কৌশল হলো বিশ্বস্ত একটি পদ্ধতির সাথে মিলিয়ে দেখা। হাজার হাজার এলোমেলো অ্যারে বানান, একই অ্যারে আপনার (বা AI-এর) sort আর একটি সরল ও নিশ্চিত পদ্ধতি (যেমন insertion sort) — দুটো দিয়েই সাজান, তারপর ফল মেলান। সাথে কিছু বিশেষ edge case-ও দিন। AI-কে এভাবে বলুন:
Sorting কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট
পঞ্চম পয়েন্টটি খেয়াল করুন। যে বাগওয়ালা sort সব ঘরে একই সংখ্যা লিখে দেয়, তার ফলও “সাজানো”! তাই প্রতিটি test case-এ দুটি শর্তই মেলান: ফল সাজানো, আর শুরুর উপাদানগুলোই ফলে আছে।
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন — তারপর “→ উত্তর” চাপুন। এগুলোই আপনাকে কোড-লেখক থেকে সিস্টেম-চিন্তক বানাবে।
প্র ০১Merge sort-এর worst case ভালো, quicksort-এর খারাপ — তবু বাস্তবের library কেন quicksort-ভিত্তিক পদ্ধতিই বেশি ব্যবহার করে, আর আলাদা আলাদা পদ্ধতি মেশায়?
কারণ Big-O শুধু কাজের হার বলে, আসল সময় বলে না। দুটি পদ্ধতিই n log n হলেও আসল যন্ত্রে তাদের গতির পার্থক্য কয়েক গুণ হতে পারে।
- Cache-এর সুবিধা: quicksort-এর partition অ্যারের ওপর বাঁ থেকে ডানে একটানা হাঁটে, আর একই অ্যারের ভেতরেই কাজ করে। CPU-র cache এই ধরনের পড়া খুব পছন্দ করে। merge sort প্রতি স্তরে ডেটা আরেকটি অ্যারেতে কপি করে, ফলে মেমরিতে দ্বিগুণ চলাচল।
- বাড়তি মেমরি: merge sort-এর n ঘরের বাড়তি জায়গা ছোট embedded যন্ত্রে থাকেই না।
- খারাপ অবস্থা বিরল ও প্রতিরোধযোগ্য: ভালো pivot নিয়ম থাকলে n² প্রায় কখনো ঘটে না। আর ঘটলেও introsort-এর মতো সুরক্ষা আছে — recursion খুব গভীরে গেলে heapsort-এ বদলে যাওয়া। ফলে গড়ে quicksort-এর গতি, আর সবচেয়ে খারাপেও heapsort-এর n log n নিশ্চয়তা।
- ছোট টুকরোয় সরলতাই গতি: ১০-১৫টি উপাদানে recursion-এর খরচই বেশি, তাই ছোট টুকরো যায় insertion sort-এর হাতে।
তবে Python ও Java (object-এর ক্ষেত্রে) বেছে নিয়েছে merge-ভিত্তিক Timsort, কারণ সেখানে stability আবশ্যক। অর্থাৎ পছন্দটি চাহিদার ওপর নির্ভর করে: stability, মেমরি, আর ডেটা সাধারণত কেমন।
মূল উপলব্ধি: তাত্ত্বিক জটিলতা হলো প্রথম ছাঁকনি, শেষ সিদ্ধান্ত নয়। বাস্তবের প্রকৌশল মাপে আসল যন্ত্রে, আসল ডেটায় — আর প্রতিটি পদ্ধতির শক্তির জায়গায় তাকে ব্যবহার করে।
প্র ০২তুলনা করে সাজানো কেন n log n-এর চেয়ে দ্রুত হতে পারে না? এই যুক্তি কি সব পদ্ধতির জন্যই খাটে?
যেকোনো comparison sort-কে একটি বিশাল প্রশ্ন-গাছ হিসেবে ভাবা যায়। প্রতিটি শাখায় একটি প্রশ্ন: “a[i] কি a[j]-এর চেয়ে ছোট?” উত্তর হ্যাঁ হলে এক পথে, না হলে আরেক পথে। প্রতিটি পাতায় (শেষ বিন্দুতে) পৌঁছে পদ্ধতিটি জানে ঠিক কোন ক্রমে ডেটা ছিল, আর সেই অনুযায়ী সাজায়।
এখন হিসাব করুন। n-টি আলাদা মানের n! রকম ক্রম সম্ভব, আর প্রতিটির জন্য আলাদা পাতা লাগবে — দুটি আলাদা ক্রম একই পাতায় এলে একটির ফল ভুল হবেই, কারণ দুটোকে একইভাবে নড়ানো হবে। কিন্তু h গভীরতার একটি হ্যাঁ-না গাছে পাতা থাকতে পারে বড়জোর 2^h টি। তাই 2^h ≥ n!, মানে h ≥ log₂(n!). আর গাছের গভীরতা মানেই সবচেয়ে খারাপ ইনপুটে তুলনার সংখ্যা।
Stirling-এর সূত্র দিয়ে দেখানো যায় log₂(n!) প্রায় n log₂ n − ১.৪৪n. অর্থাৎ ১০ লাখ উপাদানে অন্তত প্রায় ১ কোটি ৮৫ লাখ তুলনা লাগবেই — কোনো প্রতিভা দিয়েই এর নিচে নামা যাবে না। merge sort এই সীমার খুব কাছে কাজ করে, তাই তুলনার হিসাবে সে প্রায় সর্বোত্তম।
কোথায় খাটে না? এই প্রমাণের একটি শর্ত: তথ্য পাওয়ার একমাত্র উপায় দুই উপাদানের তুলনা। counting sort বা radix sort এই শর্ত ভাঙে — তারা মানটিকে সরাসরি ঠিকানা হিসেবে ব্যবহার করে (“নম্বর ৮৫ মানে খোপ ৮৫”). একটি খোপে ফেলা মানে এক ধাপে ১০১টি সম্ভাবনার একটি বেছে নেওয়া, শুধু হ্যাঁ-না নয়। তাই তারা দেয়ালের নিচ দিয়ে চলে যায় — বিনিময়ে মানের পরিসর ছোট বা গঠন সহজ হওয়ার শর্ত মানতে হয়। Hash table-ও (পর্ব ৩৭) ঠিক এই কৌশলে খোঁজাকে প্রায় এক ধাপে নামায়।
মূল উপলব্ধি: নিম্নসীমা প্রমাণ বলে “এই নিয়মে খেললে এর চেয়ে ভালো সম্ভব নয়”. এগোনোর পথ তখন একটাই — খেলার নিয়ম বদলানো, অর্থাৎ ডেটা সম্পর্কে বাড়তি কোনো তথ্য কাজে লাগানো।
প্র ০৩ডেটা যদি RAM-এর চেয়ে বড় হয় — ধরুন ৮ GB RAM-এর কম্পিউটারে ১০০ GB-এর ফাইল সাজাতে হবে — তাহলে কী করবেন?
এখানে quicksort বা যেকোনো in-place পদ্ধতি অচল, কারণ পুরো অ্যারে একসাথে মেমরিতেই আনা যায় না। আর disk থেকে এলোমেলো জায়গায় লাফিয়ে পড়া RAM-এর তুলনায় অনেক অনেক গুণ ধীর। সমাধান হলো merge sort-এর চিন্তাকে disk-এর উপযোগী করা — একে বলে external sort.
- ধাপ ১ — টুকরো সাজানো: ফাইল থেকে যতটুকু RAM-এ আঁটে (ধরুন ৬ GB) পড়ুন, মেমরিতেই দ্রুত পদ্ধতিতে সাজান, তারপর একটি আলাদা অস্থায়ী ফাইলে লিখে ফেলুন। এভাবে ১০০ GB থেকে প্রায় ১৭টি সাজানো টুকরো-ফাইল তৈরি হবে।
- ধাপ ২ — বহুমুখী merge: ১৭টি ফাইলের প্রতিটি থেকে শুধু শুরুর অংশটুকু মেমরিতে আনুন। প্রতিবার ১৭ জনের মধ্যে সবচেয়ে ছোটটি বের করে আউটপুটে লিখুন — ব্যাংকের দুই লাইন নয়, ১৭ লাইনের কাউন্টার। কে সবচেয়ে ছোট, তা দ্রুত বের করতে priority queue কাজে লাগে।
এর সৌন্দর্য হলো: প্রতিটি ফাইল শুরু থেকে শেষ পর্যন্ত একটানা পড়া হয়, আর disk একটানা পড়ায় সবচেয়ে দ্রুত। পুরো ডেটা মাত্র দুবার পড়া ও দুবার লেখা হয়।
এটি শুধু তত্ত্ব নয়। ORDER BY দিয়ে বিশাল টেবিল সাজাতে বললে, ডেটা নির্দিষ্ট মেমরি-সীমা ছাড়ালে PostgreSQL-এর মতো database ঠিক এই external merge sort-ই ব্যবহার করে।
মূল উপলব্ধি: সেরা পদ্ধতি নির্ভর করে কোন সম্পদটি সবচেয়ে দামি তার ওপর। RAM-এ তুলনার সংখ্যা গুরুত্বপূর্ণ; disk-এ গুরুত্বপূর্ণ কতবার পড়তে হলো, আর পড়াটা একটানা কি না। ১৯৪৫ সালের merge sort আজও টিকে আছে এই কারণেই।
প্র ০৪Stability শুধু “সুন্দর থাকা”-র ব্যাপার, নাকি এর ওপর বাস্তব সফটওয়্যারের সঠিকতা নির্ভর করে?
সঠিকতাই নির্ভর করে — বিশেষ করে যখন সাজানো ধাপে ধাপে হয়।
- ধাপে ধাপে সাজানো: একটি ই-কমার্স সাইটে ব্যবহারকারী আগে “নতুন আগে” বেছে নিলেন, তারপর “দাম কম আগে”. তিনি আশা করেন একই দামের পণ্যগুলোর মধ্যে নতুনগুলো আগে থাকবে। Stable sort থাকলে এটি নিজে থেকেই হয়। Unstable হলে একই দামের পণ্যগুলো এলোমেলো হয়ে যায় — কখনো কখনো প্রতিবার পাতা খুললে ভিন্ন ক্রমে!
- পুনরুৎপাদনযোগ্যতা: unstable sort-এ সমান মানের ক্রম library-র ভেতরের খুঁটিনাটির ওপর নির্ভর করে। একই প্রোগ্রাম Linux-এ একরকম, Windows-এ আরেকরকম ফল দিতে পারে। মেধাতালিকা, লটারি বা বেতনের তালিকায় এটি আইনি বা নৈতিক প্রশ্নও তুলতে পারে — “একই নম্বর পেয়ে ও আমার আগে কেন?”
- পরীক্ষা ভেঙে যাওয়া: প্রত্যাশিত আউটপুটের সাথে মিলিয়ে দেখা test (regression test) unstable sort-এ library বদলালেই ব্যর্থ হতে পারে, যদিও কোডে কোনো ভুল নেই।
C-তে কী করবেন? qsort stable নয়, তাই দুটি পথ। এক, সমতা কখনো রাখবেন না — শেষ tie-breaker হিসেবে এমন একটি চাবি দিন যা প্রতিটি রেকর্ডে আলাদা (রোল, আইডি)। দুই, আসল ক্রম রাখতে struct-এ একটি বাড়তি member-এ আগের ঘরের নম্বর রাখুন, আর সব চাবি সমান হলে সেটি তুলনা করুন — এতে যেকোনো sort কৃত্রিমভাবে stable হয়ে যায়। এর দাম সামান্য বাড়তি মেমরি।
Python বা Java-র object sort stable হওয়ার নিশ্চয়তা দেয় বলেই সেখানকার প্রোগ্রামাররা “আগে কম গুরুত্বের চাবিতে, পরে বেশি গুরুত্বের চাবিতে” সাজানোর কৌশল নিশ্চিন্তে ব্যবহার করেন। C-তে একই কোড লিখলে নীরবে ভুল ফল আসতে পারে — এবং AI প্রায়ই অন্য ভাষার অভ্যাস C-তে বয়ে আনে।
মূল উপলব্ধি: কোনো library কী নিশ্চয়তা দেয়, আর আজ আপনার যন্ত্রে কী ঘটে গেল — এই দুটি আলাদা জিনিস। শুধু নিশ্চয়তার ওপর ভরসা করুন।
প্র ০৫কেউ কি ইচ্ছে করে এমন ইনপুট বানাতে পারে, যা আপনার সার্ভারের quicksort-কে অচল করে দেবে? এর বিরুদ্ধে সুরক্ষা কী?
হ্যাঁ, পারে — আর এটি সত্যিকারের নিরাপত্তা-ঝুঁকি। একে বলে adversarial input: সাধারণ ব্যবহারকারীর নয়, আক্রমণকারীর বানানো ইনপুট, যা পদ্ধতির সবচেয়ে খারাপ অবস্থাকে টেনে আনে।
- সহজ ক্ষেত্র: pivot নিয়ম যদি নির্দিষ্ট ও জানা হয় (যেমন সবসময় শেষ ঘর), তবে শুধু আগে থেকে সাজানো তালিকা পাঠালেই n². median-of-three-এর বিরুদ্ধেও বিশেষ ক্রম বানানো যায়।
- চতুর ক্ষেত্র: ১৯৯৯ সালে Doug McIlroy “A Killer Adversary for Quicksort” নামে একটি প্রবন্ধে দেখান, comparator-এর নিয়ন্ত্রণ পেলে একটি প্রোগ্রাম চলার সময়েই উত্তরগুলো এমনভাবে দিতে পারে যে প্রায় যেকোনো সাধারণ quicksort n²-এ নেমে যায় — আগে থেকে pivot নিয়ম জানারও দরকার পড়ে না।
- ফল: ১০ লাখ উপাদানে প্রায় ২ কোটি তুলনার বদলে প্রায় ৫০,০০০ কোটি — এক সেকেন্ডের কাজ ঘণ্টায় গড়ায়। কয়েকটি এমন অনুরোধেই সার্ভার অচল — একটি denial of service. পর্ব ৩৭-এর hash flooding-এর সাথে মিলটি লক্ষ করুন: দুই জায়গাতেই আক্রমণকারী বানায় সবচেয়ে খারাপ অবস্থা।
সুরক্ষা: (১) এলোমেলো pivot — আক্রমণকারী জানে না কোন ঘর বাছা হবে। (২) introsort-এর মতো নিশ্চিত সীমা — recursion গভীরে গেলেই heapsort, তাই worst case-ও n log n. (৩) যেখানে নিশ্চয়তা আবশ্যক, সেখানে শুরু থেকেই merge sort বা heapsort. (৪) ইনপুটের আকারের ওপর সীমা রাখা।
মূল উপলব্ধি: ইন্টারনেটের দিকে খোলা যেকোনো সফটওয়্যারে “গড়ে দ্রুত” যথেষ্ট নয় — ধরে নিন কেউ না কেউ সবচেয়ে খারাপ ইনপুটটি খুঁজে বের করবেই। Worst case তখন আর তত্ত্বের বিষয় থাকে না, নিরাপত্তার বিষয় হয়ে যায়।
অনুশীলন
বেশিরভাগ কাজ খাতা-কলমে — হাতে করে দেখাই এখানে আসল শেখা।
-
হাতে insertion sort: 4, 3, 2, 1 — এই চারটি সংখ্যা insertion sort-এ সাজান। প্রতিটি ধাপে অ্যারে লিখুন আর মোট তুলনা গুনুন। তারপর 1, 2, 3, 4-এর জন্য একই কাজ করুন।
4, 3, 2, 1: 3 তোলা → [3 4 2 1], ১টি তুলনা। 2 তোলা → [2 3 4 1], ২টি। 1 তোলা → [1 2 3 4], ৩টি। মোট ৬ = ৪ × ৩ / ২ — সবচেয়ে খারাপ অবস্থা, কারণ প্রতিটি নতুন সংখ্যাকে একদম সামনে যেতে হয়েছে।
1, 2, 3, 4: প্রতিটি নতুন সংখ্যা একবার তুলনা করেই দেখে আগেরটি ছোট, থেমে যায়। মোট ৩টি তুলনা = n − ১. এজন্যই প্রায়-সাজানো ডেটায় insertion sort এত দ্রুত।
-
Partition নিজে করুন: অ্যারে 6, 1, 8, 3, 9, 2, 4. শেষের 4-কে pivot ধরে এই পর্বের ডায়াগ্রামের নিয়মে partition করুন। শেষে 4 কোন ঘরে বসল? বাঁয়ের ও ডানের দলে কারা?
বাঁ থেকে দেখুন: 6 বড়, থাকুক। 1 ছোট → [0]-এর 6-এর সাথে বদল: 1, 6, 8, 3, 9, 2, 4. 8 বড়। 3 ছোট → [1]-এর 6-এর সাথে বদল: 1, 3, 8, 6, 9, 2, 4. 9 বড়। 2 ছোট → [2]-এর 8-এর সাথে বদল: 1, 3, 2, 6, 9, 8, 4. শেষে pivot 4 যায় [3]-এ, সেখানকার 6 যায় শেষে: 1, 3, 2, 4, 9, 8, 6.
4 বসল ঘর [3]-এ, তার চূড়ান্ত জায়গায়। বাঁয়ের দল: 1, 3, 2; ডানের দল: 9, 8, 6. খেয়াল করুন, দলের ভেতরে ক্রম এখনো এলোমেলো — সেটি পরের recursion-এর কাজ।
-
Stability শিকারি: তালিকা (নাম, নম্বর): (Rina, 80), (Sumon, 75), (Tuli, 80), (Uzzal, 75). নম্বর অনুযায়ী ছোট থেকে বড় সাজালে stable sort কী ফল দেবে? Selection sort (প্রতিবার সবচেয়ে ছোটটি খুঁজে সামনের ঘরের সাথে বদল) কী ফল দেবে?
Stable: Sumon 75, Uzzal 75, Rina 80, Tuli 80 — সমানদের আগের ক্রম অটুট।
Selection sort: প্রথম ধাপে সবচেয়ে ছোট Sumon (75), তাকে [0]-এর Rina-র সাথে বদল: Sumon, Rina, Tuli, Uzzal. দ্বিতীয় ধাপে বাকিদের সবচেয়ে ছোট Uzzal (75), তাকে [1]-এর Rina-র সাথে বদল: Sumon, Uzzal, Tuli, Rina. তৃতীয় ধাপে Tuli আর Rina সমান, কিছু বদলায় না। ফল: Sumon, Uzzal, Tuli, Rina — Rina আর Tuli-র ক্রম উল্টে গেছে! লাফ দিয়ে বদলের সময় Rina মাঝের Tuli-কে টপকে গেছে।
-
Comparator মেরামত (কোড): এই comparator-টি পরীক্ষা করুন:
int cmp(const void *a, const void *b) { return ((const Item *)a)->price - ((const Item *)b)->price; }— যেখানেpriceএকটিdouble. কী ভুল হবে? ঠিক করে লিখুন।দুটি দামের পার্থক্য
double, কিন্তু ফাংশন ফেরত দেয়int. তাই পার্থক্য ১-এর কম হলে (যেমন 99.50 আর 99.25, পার্থক্য 0.25) সেটি কেটে হয়ে যায় 0 — qsort ভাবে দুটি দাম সমান, তাই এদের ক্রম যেকোনো হতে পারে। ভগ্নাংশ সবসময় শূন্যের দিকে কাটা পড়ে: −0.5 হয় 0, 1.7 হয় 1. তাই চিহ্ন না উল্টালেও ১-এর কম সব পার্থক্য “সমান” হয়ে যায়। আর-Wall -Wextraদিয়েও কোনো warning আসে না।সঠিক রূপ:
int cmp(const void *pa, const void *pb) { double a = ((const Item *)pa)->price; double b = ((const Item *)pb)->price; return (a > b) - (a < b); }দাম যদি কখনো NaN (“সংখ্যা নয়” — যেমন 0.0/0.0-এর ফল) হতে পারে, তবে আগে সেটি আলাদা করে বাদ দিন বা শেষে পাঠান, কারণ NaN-এর সাথে সব তুলনাই মিথ্যা হয়, ফলে নিয়মটি অসংগত হয়ে যায়।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমMerge sort-এর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- অ্যারেকে মাঝখান দিয়ে দুই ভাগ করা
- প্রতিটি ভাগকে আবার ভাগ করতে থাকা
- একটি করে উপাদান থাকলে থামা — সেটি এমনিতেই সাজানো
- পাশাপাশি দুটি সাজানো ভাগের সামনের উপাদান তুলনা করে জোড়া লাগানো
- সব স্তর জোড়া লাগিয়ে একটি পুরো সাজানো অ্যারে পাওয়া
কোন ধরনের ডেটায় insertion sort সবচেয়ে ভালো কাজ করে?
- বিশাল, পুরো এলোমেলো ডেটা
- ছোট, বা প্রায় আগে থেকেই সাজানো ডেটা
- পুরো উল্টো ক্রমের ডেটা
- মানের পরিসর খুব ছোট এমন ডেটা
সবসময় শেষ ঘরকে pivot ধরা একটি quicksort-কে আগে থেকেই সাজানো অ্যারে দিলে কী হয়?
- প্রতিবার দল ভাগ খুব অসমান হয়, কাজ n²-এ পৌঁছায়
- সাথে সাথে বুঝে ফেলে, কোনো কাজই করে না
- দুই দল সমান হয়, তাই সবচেয়ে দ্রুত চলে
- ভুল ক্রমে সাজায়
তালিকা আগে রোল অনুযায়ী সাজানো। এখন নম্বর অনুযায়ী qsort করলে সমান নম্বরের শিক্ষার্থীরা কোন ক্রমে থাকবে?
- সবসময় রোলের ক্রমেই থাকবে
- নামের বর্ণানুক্রমে
- সবসময় রোলের উল্টো ক্রমে
- নিশ্চিত নয় — library ও ডেটার ওপর নির্ভর করে
int-এর জন্য comparator হিসেবে return a - b; লেখার আসল বিপদ কী?
- ফল −১, ০ বা ১ না হয়ে অন্য সংখ্যা হয়, তাই qsort বোঝে না
- খুব বড় বা বিপরীত চিহ্নের মানে overflow হয়ে উল্টো উত্তর আসতে পারে
- বিয়োগ করা খুব ধীর
- Compile-এর সময় error দেয়
কয়েক লাখ পরীক্ষার্থীর নম্বর (০–১০০) সাজাতে counting sort কেন n log n-এর চেয়েও দ্রুত হতে পারে?
- এটি আরও চালাকভাবে তুলনা করে
- এটি একসাথে অনেক CPU ব্যবহার করে
- এটি কোনো তুলনাই করে না, মানকে সরাসরি খোপের নম্বর হিসেবে ব্যবহার করে
- এটি সব নম্বর দেখে না, শুধু নমুনা দেখে
AI-এর লেখা একটি sort ফাংশন পরীক্ষার সবচেয়ে নির্ভরযোগ্য উপায় কোনটি?
- হাজারো এলোমেলো অ্যারেতে একটি বিশ্বস্ত sort-এর ফলের সাথে মেলানো, সাথে খালি, এক উপাদান, সব সমান, সাজানো ও উল্টো অ্যারে
- একটি ছোট উদাহরণ চালিয়ে দেখা
- শুধু দেখা যে ফলের প্রতিটি জোড়া ঠিক ক্রমে আছে
- AI-কেই জিজ্ঞেস করা, কোডটি ঠিক আছে কি না
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- সাজানো ডেটা খোঁজা, একই জিনিস খুঁজে পাওয়া আর র্যাংকিং সহজ করে — sorting তাই অসংখ্য কাজের প্রথম ধাপ।
- Insertion sort ছোট ও প্রায়-সাজানো ডেটায় সেরা, এলোমেলো বড় ডেটায় n².
- Merge sort সবসময় n log n ও stable, কিন্তু বাড়তি n ঘর লাগে; quicksort in-place ও সাধারণত সবচেয়ে দ্রুত, কিন্তু খারাপ pivot-এ n².
- তুলনা করে সাজালে মোটামুটি n log n-এর নিচে নামা অসম্ভব; ছোট পরিসরের মানে counting sort তুলনা ছাড়াই n + k-তে সাজায়।
- C-তে
qsort+ নির্ভুল comparator: বিয়োগ নয়,(a > b) - (a < b); qsort stable নয়, তাই সমতার নিয়ম comparator-এ লিখুন।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৪১ · সার্চিং ও Divide & Conquerপরবর্তী পর্বসাজানো ডেটায় binary search, আর ভাগ করে জয়ের কৌশল।
- C প্রোগ্রামিং · কোর্স হোম৫৬টি পর্বপুরো কোর্সের রোডম্যাপ — কোন পর্ব কখন।
- Data Structures & Algorithmsগভীরে যানHeapsort, radix sort, আর আরও অনেক sorting পদ্ধতি বিস্তারিত।
- Design & Analysis of Algorithmsগভীরে যানn log n নিম্নসীমার পূর্ণ প্রমাণ, recurrence আর quicksort-এর গড় বিশ্লেষণ।
- Database Management & SQLপাশের ট্র্যাকORDER BY, index আর বড় টেবিলে external merge sort কীভাবে চলে।