Introduction

প্রোগ্রামিংয়ে sorting বলতে বোঝায় কোনো array কে নির্দিষ্ট ক্রমে সাজানো। এই ক্রম হতে পারে ছোট থেকে বড়, বড় থেকে ছোট, অথবা alphabet অনুযায়ী।

ধরুন, একটি ক্লাসের ১০ জন শিক্ষার্থীর নম্বর আছে। এখন যদি আপনি জানতে চান কে প্রথম, কে দ্বিতীয়, বা কার নম্বর সবচেয়ে কম, তাহলে আগে নম্বরগুলো সাজাতে হবে। আবার অনলাইন শপে কম দাম থেকে বেশি দামের পণ্য দেখানো, পরীক্ষার মেধাতালিকা তৈরি করা, বা নাম alphabetically সাজানো—এসবই sorting-এর বাস্তব উদাহরণ। অর্থাৎ, sorting হলো এমন একটি মৌলিক কাজ যা ডেটাকে বুঝতে, খুঁজতে এবং ব্যবহার করতে অনেক সহজ করে দেয়।

সহজভাবে বললে, একটি array যদি হয়:

[7, 2, 9, 1, 5]

তাহলে sorting করার পর এটি হতে পারে:

Ascending order (ছোট থেকে বড়): [1, 2, 5, 7, 9]
Descending order (বড় থেকে ছোট): [9, 7, 5, 2, 1]

অর্থাৎ,array-এর ভেতরের data গুলোকে গোছানোভাবে arrange করাই হলো sorting ।

Why Sorting is Important

Programming-এ আমরা প্রায়ই অনেক data নিয়ে কাজ করি—যেমন student marks, product prices, employee salary, exam ranking, কিংবা নামের তালিকা। এই data গুলো যদি সাজানো থাকে, তাহলে সবচেয়ে ছোট, সবচেয়ে বড়, মাঝামাঝি, বা নির্দিষ্ট range-এর মান খুব সহজে খুঁজে বের করা যায়। তাই sorting data analysis-এর প্রথম ধাপগুলোর একটি হিসেবে কাজ করে।
Sorting-এর আরেকটি বড় গুরুত্ব হলো এটি searching-কে দ্রুত এবং efficient করে। একটি unsorted array-তে কোনো element খুঁজতে গেলে অনেক সময় একে একে সবগুলো value check করতে হতে পারে। কিন্তু data যদি sorted থাকে, তাহলে Binary Search-এর মতো দ্রুত algorithm ব্যবহার করা যায়, যা অনেক কম সময়ে result দেয়। বড় dataset-এর ক্ষেত্রে এটি খুবই গুরুত্বপূর্ণ।
এছাড়া অনেক programming problem সরাসরি sorting-এর সঙ্গে জড়িত। Leaderboard তৈরি, result sheet বানানো, dictionary order-এ নাম সাজানো, e-commerce site-এ low-to-high price দেখানো—এসব ক্ষেত্রেই sorting লাগে। এমনকি অনেক advanced algorithm ও problem-solving technique শুরু করার আগে data sort করে নেয়, কারণ sorted data নিয়ে logic apply করা অনেক সহজ হয়।
সহজভাবে বললে, sorting data-কে শুধু সাজায় না; এটি data-কে বোঝার, খোঁজার, তুলনা করার এবং efficiently ব্যবহার করার উপযোগী করে তোলে। তাই programming-এ sorting একটি foundation-level concept, যা প্রায় সব ধরনের software system-এ কোনো না কোনোভাবে ব্যবহৃত হয়।

List of Important Sorting Algorithms

এই article-এ আমরা Bubble Sort এবং Insertion Sort নিয়ে আলোচনা করব।

Bubble Sort

Bubble Sort-এর মূল ধারণা খুব সহজ। আমরা array-এর পাশাপাশি থাকা দুটি element তুলনা করি। যদি বাম পাশের element ডান পাশের element-এর চেয়ে বড় হয়, তাহলে তাদের জায়গা বদলে দিই। এভাবে একবার পুরো array ঘুরলে সবচেয়ে বড় element ধীরে ধীরে একদম শেষে চলে যায়। এই কারণেই এর নাম Bubble Sort— মানে পানির ভেতরে বড় bubble উপরের দিকে উঠে যাচ্ছে।

Bubble Sort Algorithm

Input: একটি array A যেখানে n টি element আছে
Output: sorted array

১. i=0 থেকে n-2 পর্যন্ত repeat করো
২. প্রতিটি pass-এ j=0 থেকে n-2-i পর্যন্ত compare করো
৩. যদি A[j]>A[j+1] হয়, তাহলে দুইটি element swap করো
৪. এভাবে প্রতিটি pass শেষে সবচেয়ে বড় element শেষের দিকে চলে যাবে
৫. সব pass শেষ হলে array sorted হবে

Pseudocode

BubbleSort(A, n)
    for i ← 0 to n - 2
        for j ← 0 to n - 2 - i
            if A[j] > A[j + 1]
                swap A[j], A[j + 1]

Bubble Sort C++ Code

#include <iostream>
using namespace std;

int main() {
    int arr[] = {5, 2, 4, 1};
    int n = 4;

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

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

Insertion Sort

Insertion Sort হলো এমন একটি sorting algorithm যেখানে array-এর element গুলোকে একে একে সঠিক জায়গায় বসানো হয়। এটি অনেকটা তাস খেলায় হাতে থাকা তাস গুছিয়ে নেওয়ার মতো। নতুন একটি তাস হাতে এলে আমরা সেটিকে আগের সাজানো তাসগুলোর মধ্যে ঠিক জায়গায় বসাই। Insertion Sort-ও ঠিক এভাবেই কাজ করে।
এই algorithm-এ আমরা ধরে নিই, শুরুতে প্রথম element-টি already sorted। তারপর দ্বিতীয় element থেকে শুরু করে প্রতিটি element-কে sorted অংশের মধ্যে সঠিক position-এ insert করা হয়। এভাবে ধীরে ধীরে পুরো array sorted হয়ে যায়।

Insertion Sort Algorithm

Input: একটি array A যেখানে n টি element আছে
Output: sorted array

১. প্রথম element-টিকে sorted ধরে নাও।
২. দ্বিতীয় element থেকে শুরু করো।
৩. বর্তমান element-টিকে key হিসেবে রাখো।
৪. key-এর আগের element গুলোর সাথে compare করো।
৫. যতক্ষণ আগের element key-এর চেয়ে বড় হবে, ততক্ষণ সেগুলোকে এক ঘর ডানে সরাও।
৬. সঠিক জায়গা পেলে সেখানে key বসিয়ে দাও।
৭. একইভাবে বাকি সব element-এর জন্য repeat করো।
৮. সব element সঠিক জায়গায় বসে গেলে array sorted হবে।

Pseudocode

InsertionSort(A, n)
    for i ← 1 to n - 1
        key ← A[i]
        j ← i - 1

        while j ≥ 0 and A[j] > key
            A[j + 1] ← A[j]
            j ← j - 1

        A[j + 1] ← key

Insertion Sort C++ Code

#include <iostream>
using namespace std;

int main() {
    int arr[] = {5, 2, 4, 1};
    int n = 4;

    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

Insertion Sort প্রতিটি নতুন element-কে আগের sorted অংশের মধ্যে সঠিক জায়গায় insert করে array-কে ধীরে ধীরে sort করে।

Time Complexity: Bubble Sort vs Insertion Sort

Bubble Sort

Best Case: O(n)
Average Case: O(n²)
Worst Case: O(n²)

কেন?

Bubble Sort-এ element গুলোকে বারবার পাশাপাশি compare করতে হয়। আর data যদি অনেকটা unsorted থাকে, তাহলে অনেক swap লাগে। তাই সাধারণভাবে এর কাজের পরিমাণ n² এর মতো বেড়ে যায়।

Insertion Sort

Best Case: O(n)
Average Case: O(n²)
Worst Case: O(n²)

কেন?

Insertion Sort-এ প্রতিটি নতুন element-কে sorted অংশে সঠিক জায়গায় বসাতে হয়। যদি array আগে থেকেই sorted বা প্রায় sorted থাকে, তাহলে খুব কম shift লাগে। কিন্তু যদি data পুরো উল্টোভাবে থাকে, তাহলে অনেক shift করতে হয়, তাই worst case O(n²) হয়।

এই part-এ আমরা sorting-এর basic idea, sorting কেন important, Bubble Sort, এবং Insertion Sort আলোচনা করলাম। এখানে দেখা গেল, দুইটির time complexity একই রকম হলেও Insertion Sort সাধারণত Bubble Sort-এর চেয়ে better choice, বিশেষ করে ছোট বা প্রায় sorted data-এর ক্ষেত্রে।