14. Basic Sorting

ডাটা সাজানো বা শর্টিং (Sorting) হলো এলিমেন্টগুলোকে একটি নির্দিষ্ট ক্রমে (যেমন: ছোট থেকে বড় বা বড় থেকে ছোট) সাজানোর পদ্ধতি। প্রোগ্রামিংয়ে এটি অন্যতম মৌলিক এবং গুরুত্বপূর্ণ কনসেপ্ট।

---

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

এটি সবচেয়ে সহজ সর্টিং অ্যালগরিদম। এতে পাশাপাশি দুটি এলিমেন্ট তুলনা করা হয় এবং ভুল ক্রমে থাকলে তাদের জায়গা অদলবদল (Swap) করা হয়। এভাবে সবচেয়ে বড় এলিমেন্টটি "বুদবুদ" এর মতো অ্যারের শেষে পৌঁছে যায়।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. অ্যারের প্রথম থেকে শুরু করে পাশাপাশি দুটি এলিমেন্ট তুলনা করুন।
2. যদি বাম পাশের এলিমেন্টটি ডান পাশেরটির চেয়ে বড় হয়, তবে তাদের জায়গা বদলান (Swap)।
3. শেষ এলিমেন্ট পর্যন্ত এটি চালিয়ে যান। প্রথম পাস শেষে সবচেয়ে বড় সংখ্যাটি শেষে পৌঁছে যাবে।
4. বাকি এলিমেন্টগুলোর জন্য একই প্রসেস পুনরায় ফলো করুন।

📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)

• Best Case: O(n) - যদি অ্যারে আগে থেকেই সর্টেড থাকে (অপ্টিমাইজড ভার্সনে)।
• Worst Case: O(n²) - যদি অ্যারেটি উল্টো ক্রমে সাজানো থাকে।
• Average Case: O(n²)
• Space Complexity: O(1) - অতিরিক্ত মেমরি লাগে না।

Java Implementation

public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break; // Already sorted
    }
}

Python Implementation

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

---

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

সিলেকশন সর্টে প্রতিবার অ্যারের অবশিষ্টাংশ থেকে ক্ষুদ্রতম এলিমেন্টটি খুঁজে বের করা হয় এবং সেটিকে সঠিক জায়গায় রাখা হয়।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. অ্যারের প্রথম ইনডেক্স থেকে শুরু করুন এবং একে "minimum" হিসেবে ধরে নিন।
2. বাকি এলিমেন্টগুলোর মধ্যে সার্চ করে সবচেয়ে ছোট (minimal) এলিমেন্টটি খুঁজে বের করুন।
3. এই নতুন ক্ষুদ্রতম এলিমেন্টটিকে বর্তমান পজিশনের এলিমেন্টের সাথে অদলবদল (Swap) করুন।
4. এভাবে প্রতিটি পজিশনের জন্য প্রসেসটি রিপিট করুন।

📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)

• Best Case: O(n²) - সব সময়ই সব এলিমেন্টকে চেক করতে হয়।
• Worst Case: O(n²)
• Average Case: O(n²)
• Space Complexity: O(1)

Java Implementation

public void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

Python Implementation

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

---

3. ইনসার্শন সর্ট (Insertion Sort)

ইনসার্শন সর্টে একটি নতুন এলিমেন্টকে তার সঠিক জায়গায় ঢুকিয়ে দেওয়া (Insert) হয়। অনেকটা হাতের তাসের মতো একে একে কার্ড গুছিয়ে রাখার মতো।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. দ্বিতীয় এলিমেন্ট থেকে শুরু করুন (ধরে নেওয়া হয় প্রথমটি সর্টেড)।
2. বর্তমান এলিমেন্টটিকে (key) তার আগের এলিমেন্টগুলোর সাথে তুলনা করুন।
3. যদি আগের এলিমেন্টটি কি-এর চেয়ে বড় হয়, তবে সেটিকে এক ঘর ডানে সরান।
4. কি-এর জন্য সঠিক জায়গা পাওয়া গেলে সেটিকে বসিয়ে দিন।
5. শেষ পর্যন্ত এটি চালিয়ে যান।

📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)

• Best Case: O(n) - যদি ডাটা আগে থেকেই সর্টেড থাকে।
• Worst Case: O(n²) - যদি ডাটা উল্টো ক্রমে থাকে।
• Average Case: O(n²)
• Space Complexity: O(1)

Java Implementation

public void insertionSort(int[] arr) {
    int n = arr.length;
    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;
    }
}

Python Implementation

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

---

4. কমপ্লেক্সিটি তুলনা (Summary)

Algorithm	Best Case	Worst Case	Space	Stability
Bubble Sort	O(n)	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(n²)	O(1)	No
Insertion Sort	O(n)	O(n²)	O(1)	Yes

---

IMPORTANT

সিলেকশন সর্ট ছোট মেমরির জন্য ভালো কারণ এতে সোয়াপিং (Swapping) খুব কম হয় কিন্তু বড় ডাটা সেটে বাবল বা সিলেকশন ব্যবহার এড়িয়ে চলা উচিত।

---

TIP

রিয়েল লাইফ সিনারিওতে বা ইন্টারভিউতে বড় ডাটার জন্য Merge Sort বা Quick Sort বেশি ব্যবহৃত হয়, যা আমরা পরবর্তী লেভেলে শিখব।