সর্টিং অ্যালগরিদম (বাবল, সিলেকশন, মার্জ, কুইক)

প্রোগ্রামিংয়ে সবচেয়ে বেশি ব্যবহার হওয়া কাজগুলোর মধ্যে একটা হলো ডেটা সাজানো বা Sorting। একটা লিস্টের সংখ্যাগুলোকে ছোট থেকে বড় (Ascending) বা বড় থেকে ছোট (Descending) সাজানোর জন্য অনেক অ্যালগরিদম আছে।

১. বাবল সর্ট (Bubble Sort)

বাবল সর্ট হলো সবচেয়ে সহজ সর্টিং অ্যালগরিদম। এটা বারবার অ্যারেটা ঘুরে দেখে এবং পাশাপাশি দুটো সংখ্যা চেক করে। যদি প্রথমটা দ্বিতীয়টার চেয়ে বড় হয়, তবে তারা জায়গা বদল (Swap) করে।

টাইম কমপ্লেক্সিটি: $O(n^2)$ স্পেস কমপ্লেক্সিটি: $O(1)$

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++)      
        for (int j = 0; j < n-i-1; j++)  
            if (arr[j] > arr[j+1])  
                swap(arr[j], arr[j+1]);  
}

২. সিলেকশন সর্ট (Selection Sort)

এই পদ্ধতিতে পুরো অ্যারে থেকে সবচেয়ে ছোট সংখ্যাটা খুঁজে বের করে সেটাকে অ্যারের একেবারে শুরুতে এনে রাখা হয়।

টাইম কমপ্লেক্সিটি: $O(n^2)$ স্পেস কমপ্লেক্সিটি: $O(1)$

৩. মার্জ সর্ট (Merge Sort)

এটি একটি Divide and Conquer (ভাগ করো এবং জয় করো) অ্যালগরিদম। এটা অ্যারেকে বারবার অর্ধেক করে ভাগ করে যতক্ষণ না প্রতিটা অংশে মাত্র ১টি এলিমেন্ট থাকে। এরপর ছোট অংশগুলোকে সর্ট করে আবারো জোড়া লাগায় (Merge)।

যেহেতু এটা বারবার অ্যারেকে অর্ধেক করে, তাই এর ইটারেশন $O(\log n)$, আর প্রতিটি ধাপে জোড়া লাগাতে $O(n)$ সময় লাগে। টাইম কমপ্লেক্সিটি: $O(n \log n)$ (খুবই ফাস্ট!) স্পেস কমপ্লেক্সিটি: $O(n)$ (অতিরিক্ত মেমরি লাগে)

৪. কুইক সর্ট (Quick Sort)

কুইক সর্টও Divide and Conquer প্রিন্সিপাল ব্যবহার করে কাজ করে। এটি অ্যারে থেকে একটি সংখ্যাকে Pivot (কেন্দ্রমূল) হিসেবে বেছে নেয়। এরপর Pivot এর চেয়ে ছোট সংখ্যাগুলোকে বামে এবং বড় সংখ্যাগুলোকে ডানে নিয়ে যায়।

অধিকাংশ ল্যাঙ্গুয়েজের Built-in sort() ফাংশনগুলো সাধারণত কুইক সর্ট এর একটা ভ্যারিয়েন্ট (যেমন: IntroSort) ব্যবহার করে। টাইম কমপ্লেক্সিটি: এভারেজ কেসে $O(n \log n)$, কিন্তু সবচেয়ে বাজে ক্ষেত্রে (Worst case) $O(n^2)$ হতে পারে। স্পেস কমপ্লেক্সিটি: $O(\log n)$ (রিকার্সিভ স্ট্যাকের জন্য)।

---

কোনটা বেস্ট? বেশিরভাগ সময়ই আমরা নিজে সর্টিং অ্যালগরিদম লিখি না, ল্যাঙ্গুয়েজের বিল্ট-ইন ফাংশন (যেমন C++ এর std::sort বা Python এর list.sort()) ব্যবহার করি। তবে এগুলোর ভেতরের লজিক জানা থাকা সফটওয়্যার ইঞ্জিনিয়ারিংয়ের জন্য খুবই জরুরি!