Sorting Algorithms সহজভাবে — Selection Sort এবং Merge Sort

Introduction

আগের part-এ আমরা sorting-এর basic idea, Bubble Sort এবং Insertion Sort নিয়ে আলোচনা করেছি। সেখানে আমরা দেখেছি, ছোট বা প্রায় sorted data-এর ক্ষেত্রে simple sorting algorithm গুলো বোঝা সহজ এবং useful।

এই part-এ আমরা আরও দুইটি গুরুত্বপূর্ণ sorting algorithm নিয়ে আলোচনা করব:

• Selection Sort
• Merge Sort

Selection Sort হলো simple comparison-based sorting algorithm, যেখানে প্রতি ধাপে সবচেয়ে ছোট element খুঁজে এনে সঠিক জায়গায় বসানো হয়। অন্যদিকে Merge Sort হলো একটু advanced algorithm, যেটি Divide and Conquer technique ব্যবহার করে array sort করে।

সহজভাবে বললে, Selection Sort আমাদের sorting-এর basic logic বুঝতে সাহায্য করে, আর Merge Sort আমাদের efficient sorting algorithm কীভাবে কাজ করে তা বুঝতে সাহায্য করে।

ধরুন, একটি array আছে:

[8, 3, 5, 1, 6]

Sorting করার পর এটি হবে:

[1, 3, 5, 6, 8]

এখন প্রশ্ন হলো, এই sorting এর কাজ Selection Sort এবং Merge Sort কীভাবে করে? চলুন ধাপে ধাপে দেখি।

Selection Sort

Selection Sort-এর idea খুব সহজ। পুরো array থেকে সবচেয়ে ছোট element খুঁজে বের করা হয় এবং সেটিকে প্রথম position-এ বসানো হয়। এরপর বাকি unsorted অংশ থেকে আবার সবচেয়ে ছোট element খুঁজে দ্বিতীয় position-এ বসানো হয়। এভাবে ধীরে ধীরে array sorted হয়ে যায়।

এটি অনেকটা এমন—ধরুন আপনার সামনে কয়েকজন student-এর marks আছে। আপনি প্রথমে সবচেয়ে কম marks পাওয়া student খুঁজে list-এর শুরুতে রাখলেন। তারপর বাকি studentদের মধ্যে আবার সবচেয়ে কম marks খুঁজলেন এবং দ্বিতীয় position-এ রাখলেন। এভাবেই list sorted হয়ে যাবে।

সহজভাবে বললে, Selection Sort প্রতি ধাপে minimum element select করে সঠিক জায়গায় বসায়।

Selection Sort Algorithm

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

১. প্রথম position থেকে শুরু করো।
২. পুরো unsorted অংশের মধ্যে সবচেয়ে ছোট element খুঁজে বের করো।
৩. সবচেয়ে ছোট element-এর index মনে রাখো।
৪. সেটিকে current position-এর element-এর সাথে swap করো।
৫. এরপর next position-এ যাও।
৬. একইভাবে প্রতিবার unsorted অংশ থেকে minimum element খুঁজে সামনে বসাও।
৭. সব position check শেষ হলে array sorted হবে।

Pseudocode

SelectionSort(A, n)
    for i ← 0 to n - 2
        minIndex ← i

        for j ← i + 1 to n - 1
            if A[j] < A[minIndex]
                minIndex ← j

        swap A[i], A[minIndex]

Selection Sort C++ Code

#include <iostream>
using namespace std;

int main() {
    int arr[] = {8, 3, 5, 1, 6};
    int n = 5;

    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;

        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        swap(arr[i], arr[minIndex]);
    }

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

    return 0;
}

How Selection Sort Works Step by Step

ধরি array:

[8, 3, 5, 1, 6]

Pass 1

পুরো array থেকে সবচেয়ে ছোট element হলো 1। এখন 1 কে first position-এর element 8 এর সাথে swap করা হবে।

[1, 3, 5, 8, 6]

Pass 2

এখন first element sorted ধরে বাকি অংশ দেখি:

[3, 5, 8, 6]
এখানে সবচেয়ে ছোট element হলো 3, যা already সঠিক জায়গায় আছে। তাই বড় কোনো change হবে না।
[1, 3, 5, 8, 6]

Pass 3

এখন বাকি অংশ:
[5, 8, 6]

সবচেয়ে ছোট element হলো 5, এটিও already সঠিক জায়গায় আছে।
[1, 3, 5, 8, 6]

Pass 4

এখন বাকি অংশ:
[8, 6]
সবচেয়ে ছোট element হলো 6, তাই 8 এবং 6 swap হবে।
[1, 3, 5, 6, 8]

এখন array sorted।

Time Complexity of Selection Sort

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

কেন?

Selection Sort-এ array already sorted থাকলেও প্রতিবার minimum element খুঁজতে হয়। অর্থাৎ, প্রতিটি pass-এ বাকি element গুলো compare করা লাগে। তাই best case, average case, এবং worst case—সব ক্ষেত্রেই time complexity O(n²)।
তবে Selection Sort-এর একটি ভালো দিক হলো এটি অনেক বেশি swap করে না। প্রতি pass-এ সাধারণত একবার swap হয়। তাই যেখানে swap operation costly, সেখানে Selection Sort কিছু ক্ষেত্রে useful হতে পারে।

Merge Sort

Merge Sort হলো একটি efficient sorting algorithm, যেটি Divide and Conquer technique ব্যবহার করে।
Divide and Conquer মানে হলো বড় problem-কে ছোট ছোট problem-এ ভাগ করা, তারপর ছোট problem গুলোর solution combine করে final answer বের করা।
Merge Sort-এ array-কে বারবার দুই ভাগে ভাগ করা হয়, যতক্ষণ না প্রতিটি ভাগে একটিমাত্র element থাকে। কারণ একটি single element naturally sorted। তারপর সেই ছোট sorted অংশগুলোকে merge করে বড় sorted array বানানো হয়।

সহজভাবে বললে:
১. Array ভাগ করো
২. ছোট অংশগুলো sort করো
৩. sorted অংশগুলো merge করো

Merge Sort Algorithm

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

১. যদি array-তে একটিমাত্র element থাকে, তাহলে সেটি already sorted।
২. array-কে মাঝখান থেকে দুই ভাগে ভাগ করো।
৩. left half কে recursively sort করো।
৪. right half কে recursively sort করো।
৫. দুইটি sorted half কে merge করে final sorted array তৈরি করো।

Pseudocode

MergeSort(A, left, right)
    if left < right
        mid ← (left + right) / 2

        MergeSort(A, left, mid)
        MergeSort(A, mid + 1, right)

        Merge(A, left, mid, right)

Merge(A, left, mid, right)
    leftPart ← A[left...mid]
    rightPart ← A[mid+1...right]

    compare elements from leftPart and rightPart
    place smaller element into original array

    copy remaining elements if any

Merge Sort C++ Code

#include <iostream>
using namespace std;

void mergeArray(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int leftArr[n1];
    int rightArr[n2];

    for (int i = 0; i < n1; i++) {
        leftArr[i] = arr[left + i];
    }

    for (int j = 0; j < n2; j++) {
        rightArr[j] = arr[mid + 1 + j];
    }

    int i = 0;
    int j = 0;
    int k = left;

    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        mergeArray(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {8, 3, 5, 1, 6};
    int n = 5;

    mergeSort(arr, 0, n - 1);

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

    return 0;
}

How Merge Sort Works Step by Step

ধরি array:
[8, 3, 5, 1, 6]

প্রথমে array-টি দুই ভাগে ভাগ হবে:
[8, 3, 5] [1, 6]

আবার ভাগ হবে:
[8, 3] [5] [1] [6]

আরও ভাগ করলে:
[8] [3] [5] [1] [6]
এখন প্রতিটি single element sorted। এবার merge করা শুরু হবে।

প্রথমে:
[8] এবং [3] merge করলে হবে [3, 8]

এরপর:
[3, 8] এবং [5] merge করলে হবে [3, 5, 8]

অন্যদিকে:
[1] এবং [6] merge করলে হবে [1, 6]

এখন final merge:
[3, 5, 8] এবং [1, 6]

sortedভাবে merge করলে হবে:
[1, 3, 5, 6, 8]
এভাবেই Merge Sort array-কে divide করে, তারপর sortedভাবে merge করে final result তৈরি করে।

Time Complexity of Merge Sort

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

কেন?

Merge Sort প্রতি ধাপে array-কে দুই ভাগে ভাগ করে। একটি array বারবার অর্ধেক করলে মোট ভাগ করার level হয় প্রায় log n। আবার প্রতিটি level-এ সব element একবার করে merge করতে হয়, যার কাজের পরিমাণ n।
তাই total time complexity হয়:

O(n log n)

Merge Sort-এর performance Bubble Sort, Insertion Sort, এবং Selection Sort-এর তুলনায় অনেক ভালো, বিশেষ করে বড় data-এর ক্ষেত্রে।

তবে Merge Sort-এর একটি limitation আছে। এটি extra memory ব্যবহার করে, কারণ merge করার সময় temporary array দরকার হয়। তাই এর space complexity সাধারণত O(n)।

Which One is Better?

Selection Sort বুঝতে সহজ, কিন্তু efficient নয়। ছোট array বা learning purpose-এর জন্য এটি ভালো। তবে বড় data sort করার জন্য Selection Sort ভালো choice নয়, কারণ এর time complexity O(n²)।
Merge Sort তুলনামূলকভাবে complex হলেও অনেক বেশি efficient। বড় dataset sort করতে Merge Sort অনেক ভালো কাজ করে, কারণ এর time complexity সব case-এ O(n log n)।

সহজভাবে বললে:
ছোট এবং simple learning example-এর জন্য: Selection Sort
বড় data এবং efficient sorting-এর জন্য: Merge Sort

এই part-এ আমরা Selection Sort এবং Merge Sort নিয়ে আলোচনা করলাম।