Sorting Algorithms (All)

ভূমিকা (Introduction to Sorting)

সর্টিং (Sorting) হলো কম্পিউটার সায়েন্সের অন্যতম গুরুত্বপূর্ণ এবং বেসিক একটি কনসেপ্ট। সর্টিং বলতে বোঝায় এলোমেলোভাবে থাকা কিছু ডেটাকে (যেমন- সংখ্যা, শব্দ, নাম ইত্যাদি) একটি নির্দিষ্ট ক্রমানুসারে (ছোট থেকে বড় অথবা বড় থেকে ছোট) সাজানো। আমরা যখন অনলাইনে কোনো শপে Price "Low to High" দিয়ে সার্চ করি, কিংবা ফোনের কন্ট্যাক্ট লিস্টে নামগুলো A-Z আকারে দেখি, তখন ব্যাকএন্ডে কোনো না কোনো সর্টিং অ্যালগরিদম কাজ করে।

এই পোস্টে আমরা বহুল ব্যবহৃত ৫টি সর্টিং অ্যালগরিদম নিয়ে বিস্তারিত আলোচনা করব এবং C ভাষায় তৈরি একটি অসাধারণ Sorting Visualizer প্রোজেক্ট সম্পর্কে জানব।

---

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

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

কীভাবে কাজ করে?

এটি অ্যারের প্রথম উপাদান থেকে শুরু করে পাশাপাশি দুটি উপাদানের তুলনা করে। যদি প্রথম উপাদানটি দ্বিতীয়টির চেয়ে বড় হয়, তবে তারা নিজেদের জায়গা বদল (Swap) করে। এভাবে পুরো অ্যারেটি একবার চেক করলে সবচেয়ে বড় উপাদানটি শেষে চলে যায়। এই প্রসেসটি বারবার চলতে থাকে যতক্ষণ না পুরো অ্যারেটি সর্ট হয়।

Time & Space Complexity:

• Best Case Time Complexity: $O(n)$ (যদি অ্যারেটি আগে থেকেই সর্ট করা থাকে)
• Worst & Average Case Time Complexity: $O(n^2)$
• Space Complexity: $O(1)$ (ইন-প্লেস অ্যালগরিদম)

C Pseudocode:

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 (সিলেকশন সর্ট)

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

কীভাবে কাজ করে?

এটি প্রথমে পুরো অ্যারে ঘুরে সবচেয়ে ছোট উপাদানটি বের করে এবং সেটিকে অ্যারের প্রথম উপাদানের সাথে সোয়াপ (Swap) করে। এরপর দ্বিতীয় উপাদান থেকে শুরু করে বাকি অ্যারের মধ্যে সবচেয়ে ছোটটি বের করে দ্বিতীয় স্থানে রাখে। এভাবে পুরো অ্যারে সর্ট করা হয়।

Time & Space Complexity:

• Time Complexity (All Cases): $O(n^2)$
• Space Complexity: $O(1)$

C Pseudocode:

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

---

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

ইনসার্শন সর্টের কনসেপ্টটা হলো তাস খেলার মতো। আমরা যখন হাত দিয়ে তাস সাজাই, তখন একটা করে তাস তুলি এবং সেটি আগে থেকে সাজানো তাসের সঠিক স্থানে ঢুকিয়ে (insert) দিই।

কীভাবে কাজ করে?

অ্যারের দ্বিতীয় উপাদান থেকে শুরু করে সেটিকে একটি ভেরিয়েবলে (key) রাখা হয়। এরপর এর আগের উপাদানগুলোর সাথে তুলনা করে সঠিক জায়গায় বসানো হয়।

Time & Space Complexity:

• Best Case Time Complexity: $O(n)$
• Worst & Average Case Time Complexity: $O(n^2)$
• Space Complexity: $O(1)$

C Pseudocode:

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;
}

---

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

মার্জ সর্ট একটি অত্যন্ত ইফিশিয়েন্ট এবং পাওয়ারফুল সর্টিং অ্যালগরিদম যা Divide and Conquer (ভাগ করো এবং জয় করো) পদ্ধতিতে কাজ করে।

কীভাবে কাজ করে?

পুরো অ্যারেকে প্রথমে মাঝখান থেকে সমান দুই ভাগে ভাগ করা হয়। এরপর এই ভাগগুলোকে আবার ভাগ করা হয় যতক্ষণ না প্রতিটি ভাগে মাত্র একটি করে উপাদান থাকে। এরপর ছোট ছোট ভাগগুলোকে সর্ট করে করে জোড়া (Merge) লাগানো হয়, যা শেষমেশ একটি সম্পূর্ণ সর্টেড অ্যারে তৈরি করে।

Time & Space Complexity:

• Time Complexity (All Cases): $O(n \log n)$
• Space Complexity: $O(n)$ (নতুন একটি অ্যারে লাগে মার্জ করার জন্য)

---

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

কুইক সর্টও Divide and Conquer পদ্ধতিতে কাজ করে, তবে এটি মার্জ সর্টের চেয়েও বেশি ব্যবহৃত হয় কারণ এটি মেমোরি কম ব্যবহার করে।

কীভাবে কাজ করে?

এতে যেকোনো একটি উপাদানকে "Pivot" (কেন্দ্রবিন্দু) ধরা হয়। এরপর অ্যারের বাকি উপাদানগুলোকে এমনভাবে সাজানো হয় যেন Pivot এর চেয়ে ছোট সংখ্যাগুলো এর বামে এবং বড়গুলো ডানে চলে যায়। এরপর বাম এবং ডান অংশের জন্য একই কাজ রিকার্সিভলি (Recursively) করা হয়।

Time & Space Complexity:

• Best & Average Case Time Complexity: $O(n \log n)$
• Worst Case Time Complexity: $O(n^2)$ (খুবই রেয়ার)
• Space Complexity: $O(\log n)$ (রিকার্শন স্ট্যাকের জন্য)

---

💻 Sorting Visualizer (C Project)

সর্টিং অ্যালগরিদমগুলো কীভাবে কাজ করে তা বাস্তবে দেখার জন্য আমি C Programming দিয়ে একটি অসাধারণ কনসোল-বেইজড Sorting Visualizer তৈরি করেছি। এটি সরাসরি আপনার কমান্ড প্রম্পটে (Terminal) বার-চার্ট (Bar Chart) আকারে সর্টিংয়ের প্রতিটি স্টেপ অ্যানিমেশন দিয়ে দেখাবে!

🔗 প্রোজেক্ট লিংক: Sorting-Visualizer GitHub Repository

প্রোজেক্টটির ফিচারসমূহ:

1. Interactive Console UI: সম্পূর্ণ রঙিন কনসোল ইন্টারফেস।
2. Animation: সোয়াপিং এবং কম্পারিজন গুলো লাল-সবুজ রঙ দিয়ে লাইভ দেখানো হয়।
3. Speed Control: সর্টিং চলাকালীন + এবং - বাটন চেপে অ্যানিমেশনের স্পিড কন্ট্রোল করা যায়!
4. Multiple Algorithms: এতে Bubble Sort, Selection Sort, Insertion Sort, এবং Merge Sort অন্তর্ভুক্ত করা আছে।

কীভাবে চালাবেন?

আপনার পিসিতে যদি GCC কম্পাইলার থাকে, তবে টার্মিনালে নিচের কমান্ডটি রান করলেই হবে:

gcc shorting_visualization.c -o visualizer
./visualizer

এই প্রোজেক্টটির মাধ্যমে আপনি খুব সহজেই ভিজ্যুয়ালি বুঝতে পারবেন কোন অ্যালগরিদম কীভাবে এবং কত দ্রুত কাজ করে।

---

উপসংহার

সর্টিং অ্যালগরিদমগুলো কম্পিউটার সায়েন্সের অন্যতম বেসিক ভিত্তি। Bubble বা Selection Sort শিখতে সহজ হলেও, রিয়েল ওয়ার্ল্ড অ্যাপ্লিকেশন এবং বড় ডেটা সেটের জন্য সবসময় Merge Sort বা Quick Sort ব্যবহার করা হয়। আশা করি এই পোস্ট এবং আমার Sorting Visualizer প্রোজেক্টটি আপনার অ্যালগরিদম শেখার পথকে আরও সহজ করবে!