Sorting Algorithm: How Does a Computer Sort Millions of Data? ·

ভাবুন, আপনার সামনে ১০টা number আছে 8, 3, 1, 9, 4, 2, 7, 5, 6, 10। এগুলোকে ছোট থেকে বড় সাজানো খুব একটা কঠিন মনে হবে না। আপনি হয়তো চোখের সামনে দেখেই একটা একটা করে সাজিয়ে ফেলতে পারবেন।

কিন্তু একই কাজ যদি করতে দেওয়া হয় ১০ লাখ বা ১ কোটি data-র সঙ্গে?

তখন কিন্তু ব্যাপারটা আর এত সহজ থাকে না।

Computer-এর কাছে data sort করা একটা খুব common কাজ। Search result দেখানো, database থেকে information সাজানো, leaderboard তৈরি করা, e-commerce product price অনুযায়ী সাজানো অনেক জায়গাতেই sorting দরকার হয়।

আর এখানেই আসে Sorting Algorithm

Sorting Algorithm মূলত এমন কিছু step বা strategy, যার মাধ্যমে computer একটি collection of data-কে নির্দিষ্ট order-এ সাজায় যেমন ascending বা descending order।

কিন্তু interesting ব্যাপার হলো, একটা data sort করার জন্য শুধু একটা algorithm নেই।

Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort এতগুলো algorithm কেন?

কারণ সব situation একরকম নয়।

What Is a Sorting Algorithm?

সহজভাবে বললে, Sorting Algorithm হলো এমন একটি algorithm যা unordered data-কে একটি নির্দিষ্ট order-এ arrange করে।

যেমন:

Before:
7, 2, 9, 1, 5

After:
1, 2, 5, 7, 9

এটা ascending order।

আবার:

9, 7, 5, 2, 1

হলে সেটা descending order। actually sorting শুধু number-এর ক্ষেত্রে হয় না। আপনি চাইলে:

Student-এর marks
Product-এর price
User-এর name
Website-এর rating
Employee-এর salary
Date
Search result

এসবও sort করতে পারেন।

Why Do We Need Sorting Algorithms?

এখানে একটা interesting প্রশ্ন আসে data sort করবই বা কেন? কারণ sorted data নিয়ে কাজ করা অনেক সহজ।

ধরুন, একটা online shopping website-এ ৫ লাখ product আছে। User বলল:

“Price: Low to High”

এখন website-কে সেই productগুলো price অনুযায়ী সাজিয়ে দেখাতে হবে।

আবার কেউ বলল:

“Highest Rated”

তখন rating অনুযায়ী sort করতে হবে।

আর sorting অনেক সময় searching-কেও faster করে তুলতে পারে।

যেমন, unsorted data-তে কোনো value খুঁজতে আপনাকে অনেকগুলো item check করতে হতে পারে। কিন্তু data যদি properly sorted থাকে, কিছু ক্ষেত্রে আপনি Binary Search-এর মতো efficient technique ব্যবহার করতে পারবেন।

অর্থাৎ sorting শুধু data সুন্দর করে সাজানোর জন্য না। এটা efficient data processing-এর একটা important building block।

The Big Question: Which Sorting Algorithm Is Best?

এখানেই আসল মজা। আপনি যদি জিজ্ঞেস করেন,

“সবচেয়ে ভালো sorting algorithm কোনটা?”

এর simple answer হলো There is no single best sorting algorithm. কারণ algorithm-এর performance depend করে:

Data কত বড়
Data already sorted কিনা
Memory কত available
Speed কতটা important
Stable sorting দরকার কিনা
In-place sorting দরকার কিনা

একটা algorithm ছোট data-তে ভালো perform করতে পারে, কিন্তু huge dataset-এ terrible হতে পারে। তাই একজন ভালো programmer শুধু algorithm-এর নাম জানে না।

সে বুঝতে পারে:

কোন situation-এ কোন algorithm ব্যবহার করা উচিত এবং কেন।

Understanding Time Complexity

Sorting algorithm compare করার সময় সবচেয়ে important conceptগুলোর একটি হলো Time Complexity।

Time Complexity বলে দেয় input size বাড়লে algorithm-এর running time কীভাবে বাড়তে পারে। ধরুন আপনার কাছে ১০টা item আছে।

তারপর সেটা হলো: 100 → 1,000 → 10,000 → 1,000,000

Input যত বাড়বে, algorithm-এর কাজও বাড়বে। এখানেই Big-O notation আসে। Common complexities:

O(1)
O(log n)
O(n)
O(n log n)
O(n²)

Sorting-এর ক্ষেত্রে সাধারণত আমরা বিশেষভাবে দেখি: O(n²) বনাম O(n log n)

কারণ বড় data-এর ক্ষেত্রে differenceটা enormous হতে পারে।

Bubble Sort: Simple but Slow

Bubble Sort সম্ভবত সবচেয়ে famous sorting algorithmগুলোর একটি। এটার idea খুব simple। Adjacent দুইটা value compare করা হবে।

যদি ভুল order-এ থাকে, তাহলে তাদের swap করা হবে। যেমন:

5  3  8  4

প্রথমে:

5 > 3

তাই swap:

3  5  8  4

তারপর:

5 < 8

তাই কিছু করার দরকার নেই। তারপর:

8 > 4

swap:

3  5  4  8

এভাবে বারবার চলতে থাকে।

Bubble Sort-এর average এবং worst-case time complexity সাধারণত: O(n²) ছোট data-এর জন্য এটা understandable হলেও বড় data-এর ক্ষেত্রে inefficient।

তাহলে প্রশ্ন: Bubble Sort এত famous কেন?

কারণ এটা শেখার জন্য খুব easy এবং sorting-এর basic concept বুঝতে excellent। কিন্তু production system-এ huge dataset sort করার জন্য সাধারণত এটা আপনার first choice হবে না।

Selection Sort: বারবার Minimum খুঁজুন

Selection Sort-এর idea একটু different। ধরুন:

7  3  5  1  9

প্রথমে পুরো array থেকে smallest value খুঁজে বের করলাম। Smallest:

তারপর সেটাকে প্রথম position-এ নিয়ে আসলাম।

1  3  5  7  9

তারপর remaining অংশ থেকে smallest খুঁজব। এভাবে পুরো array সাজানো হবে।

Selection Sort-এর time complexity সাধারণত: O(n²) এর advantage হলো concept simple এবং swap-এর সংখ্যা কিছু ক্ষেত্রে কম হতে পারে।

কিন্তু বড় dataset-এর জন্য এটাও খুব efficient না।

Insertion Sort: Cards দিয়ে বুঝুন

Insertion Sort বোঝার সবচেয়ে সহজ example হলো playing cards।

আপনি যখন হাতে card নেন, সাধারণত একটার পর একটা card এমন জায়গায় insert করেন যাতে আপনার hand sorted থাকে।

ধরুন:

তারপর পেলেন:

তাহলে 3-কে 5-এর আগে বসাবেন।

3 5

তারপর পেলেন:

তাহলে:

3 4 5

এই idea-টাই Insertion Sort।

এটা small বা nearly sorted data-এর ক্ষেত্রে surprisingly useful হতে পারে। Average এবং worst-case complexity: O(n²)

কিন্তু best-case প্রায়: O(n) যখন data already sorted বা প্রায় sorted থাকে।

Merge Sort: Divide and Conquer

এখন আসি আরও powerful approach-এ। Merge Sort-এর মূল idea:

Divide and Conquer

মানে বড় problem-কে ছোট ছোট problem-এ ভাগ করুন। ধরুন:

8  3  7  4  2  6  1  5

এটাকে ভাগ করলাম:

8  3  7  4
2  6  1  5

তারপর আবার ভাগ:

এভাবে ছোট হতে হতে individual element-এ পৌঁছাব। তারপর sorted way-তে merge করব। Merge Sort-এর major advantage:

O(n log n) Average এবং worst-case দুই ক্ষেত্রেই। তবে এর জন্য additional memory দরকার হতে পারে।

Quick Sort: নামের মতোই কি Quick?

Quick Sort-ও Divide and Conquer strategy ব্যবহার করে। এখানে একটা element select করা হয়, যাকে বলা হয় Pivot।

তারপর data-কে pivot-এর তুলনায় ভাগ করা হয়। যেমন:

7  2  9  4  1  6

ধরলাম:

Pivot = 6

তাহলে এক পাশে থাকবে 6-এর চেয়ে ছোট value, আর অন্য পাশে বড় value। তারপর দুই side-কে আবার recursively sort করা হবে। Average case-এ Quick Sort: O(n log n)

তবে bad pivot selection হলে worst-case: O(n²)

এখানেই একটা important engineering lesson আছে:

Algorithm শুধু জানলেই হবে না, তার behaviour এবং edge cases-ও বুঝতে হবে।

Heap Sort: Heap-এর Power Use করুন

Heap Sort-এর ক্ষেত্রে আমরা Heap Data Structure ব্যবহার করি।

এমনভাবে data organize করে যাতে maximum বা minimum element efficiently পাওয়া যায়।

Max Heap ব্যবহার করলে বড় element সহজে পাওয়া যায়। Heap Sort-এর time complexity: O(n log n)

এর একটা advantage হলো predictable performance।

তবে practical performance-এর ক্ষেত্রে কোন sorting algorithm ভালো হবে সেটা environment এবং implementation-এর ওপরও depend করতে পারে।

Sorting Algorithm Comparison

এক নজরে কিছু popular sorting algorithm:

Algorithm	Best Case	Average Case	Worst Case
Bubble Sort	O(n)	O(n²)	O(n²)
Selection Sort	O(n²)	O(n²)	O(n²)
Insertion Sort	O(n)	O(n²)	O(n²)
Merge Sort	O(n log n)	O(n log n)	O(n log n)
Quick Sort	O(n log n)	O(n log n)	O(n²)
Heap Sort	O(n log n)	O(n log n)	O(n log n)

তবে শুধু এই table দেখে সিদ্ধান্ত নেওয়া উচিত না। কারণ real-world performance শুধু Big-O দিয়ে determine হয় না।

Stable vs Unstable Sorting

Sorting-এর আরেকটা interesting concept হলো Stability। ধরুন দুইজন student-এর marks একই:

Arif - 90
Rahim - 90

তাদের আগে থেকেই একটা order আছে।

Stable sorting হলে equal values-এর ক্ষেত্রে তাদের original relative order preserve হতে পারে।

এটা বিশেষ করে multiple criteria দিয়ে data sort করার সময় useful হতে পারে। যেমন প্রথমে: Department

তারপর: Salary তারপর: Name এখানে stability important হতে পারে।

In-Place Sorting

আরেকটা concept হলো In-Place Sorting।

এখানে algorithm sorting করার সময় খুব বেশি additional memory ব্যবহার না করে মূল data structure-এর মধ্যেই কাজ করার চেষ্টা করে।

Memory constraint থাকলে এটা important consideration হতে পারে। তাই algorithm নির্বাচন করার সময় শুধু: কোনটা fastest?

এটা প্রশ্ন না। বরং:

আমার memory constraint কী? Data কত বড়? Data-এর current state কী? Stable sorting দরকার?

এসবও ভাবতে হবে।

Real-World Sorting: It’s Not Just About Algorithms

এখানে একটা important বিষয় আছে।

Real-world software development-এ আপনাকে সবসময় নিজে Bubble Sort বা Quick Sort implement করতে হবে না।

অনেক programming language এবং standard library-তেই optimized sorting function থাকে। যেমন JavaScript-এ:

numbers.sort((a, b) => a - b);

আপনার কাজ অনেক সময় algorithm implement করা নয়।

আপনার কাজ হলো কেন sorting দরকার, কীভাবে data sort করতে হবে এবং কোন constraints মাথায় রাখতে হবে সেটা বুঝতে পারা।

এটাই programming-এর bigger picture।

How Do You Choose the Right Sorting Algorithm?

একটা practical decision-making mindset হতে পারে:

Small Dataset?

Simple algorithm acceptable হতে পারে।

Nearly Sorted Data?

Insertion Sort ভালো option হতে পারে।

Guaranteed O(n log n) দরকার?

Merge Sort বা Heap Sort consider করা যেতে পারে।

Average-case performance গুরুত্বপূর্ণ?

Quick Sort অনেক ক্ষেত্রে strong choice হতে পারে।

Memory constraint আছে?

In-place approaches consider করতে হবে। অর্থাৎ:

Algorithm → Data → Constraint → Trade-off → Decision

এই চিন্তার process-টাই আসল।

The Bigger Lesson Behind Sorting Algorithms

Sorting Algorithms শেখার সবচেয়ে বড় benefit হলো Bubble Sort বা Quick Sort মুখস্থ করা না।

বরং এগুলো আপনাকে একটা গুরুত্বপূর্ণ engineering mindset শেখায়। ধরুন আপনার কাছে একটা problem আছে।

আপনি প্রথমে একটা solution বানালেন। Solution কাজ করছে।

কিন্তু data ১০০ গুণ বেড়ে গেল। এখন? Solution এখনও technically correct, কিন্তু practically useless।

এখানেই একজন programmer-এর চিন্তা বদলাতে হয়। সে ভাববে: আমার solutionটা কতটা scalable? Input বড় হলে কী হবে? Memory usage কেমন?

আরও efficient approach আছে? এই mindset-টাই DSA-এর আসল value।

Final Thoughts

Sorting Algorithms দেখতে ছোট একটা programming topic মনে হলেও এর ভিতরে আসলে programming-এর অনেক বড় একটা lesson লুকিয়ে আছে।

Bubble Sort থেকে Quick Sort পর্যন্ত journey আমাদের শেখায় একটা problem-এর একাধিক solution থাকতে পারে।

কিন্তু সব solution সমান না। কোনো solution simple হতে পারে, কোনোটা fast হতে পারে, কোনোটা কম memory ব্যবহার করতে পারে, আবার কোনোটা specific type of data-এর জন্য better হতে পারে।

তাই একজন ভালো programmer শুধু জিজ্ঞেস করে না: এটা কাজ করবে?

সে আরও জিজ্ঞেস করে: এটা বড় data-এর ক্ষেত্রেও কাজ করবে?

আর সেখান থেকেই coding ধীরে ধীরে engineering হয়ে ওঠে।

Sorting Algorithms শেখার আসল উদ্দেশ্য তাই data সাজানো না better decisions নিতে শেখা।