সর্টিং৭ মিনিট পড়া

বেসিক সোর্টস (Basic Sorts)

হাতের তাসগুলো সাজানো — তিনটি উপায়, একটি গতিপথ
bubble sort:\(O(n^2)\) — প্রতিবেশীর সাথে অদলবদল (swap neighbors)selection sort:\(O(n^2)\) — সর্বনিম্ন মানটি খুঁজে বের করা (find minimum)insertion sort:\(O(n)\) সেরা ক্ষেত্রে · \(O(n^2)\) সবচেয়ে খারাপ ক্ষেত্রেstable:বাবল সোর্ট (Bubble) ✓ · ইনসার্শন সোর্ট (Insertion) ✓ · সিলেকশন সোর্ট (Selection) ✗

কল্পনা করুন আপনাকে কিছু খেলার তাস দেওয়া হয়েছে এবং আপনি সেগুলো ক্রমানুসারে সাজাতে চান। মানুষের স্বভাবজাত পদ্ধতিতে এটি করার তিনটি সাধারণ উপায় রয়েছে:

বিকল্প ক (Option A): বাঁ থেকে ডান দিকে চোখ বুলান, যদি কোনো দুটি পাশাপাশি তাস ঠিক ক্রমানুসারে না থাকে তবে তাদের স্থান অদলবদল বা সোয়াপ (swap) করুন। তাসগুলো পুরোপুরি সাজানো না হওয়া পর্যন্ত এটি পুনরাবৃত্তি করুন। এটিই হলো বাবল সোর্ট (bubble sort)।

বিকল্প খ (Option B): আপনার হাতে থাকা অগোছালো তাসগুলোর মধ্যে সবচেয়ে ছোট মানের তাসটি খুঁজে বের করুন, সেটিকে টান দিয়ে বের করে সাজানো তাসগুলোর সাথে ক্রমানুসারে আলাদা করে রাখুন। এটি পুনরাবৃত্তি করুন। এটিই হলো সিলেকশন সোর্ট (selection sort)।

বিকল্প গ (Option C): একসঙ্গে একটি করে তাস তুলুন এবং ইতিমধ্যে আপনার হাতে থাকা সাজানো তাসগুলোর মধ্যে এটিকে ঠিক সঠিক জায়গায় স্লাইড করে বসিয়ে দিন। এটিই হলো ইনসার্শন সোর্ট (insertion sort)।

সবচেয়ে খারাপ বা ওয়ার্স্ট কেসে (worst case) এই তিনটি পদ্ধতিরই টাইম কমপ্লেক্সিটি (time complexity) হলো \(O(n^2)\)। কিন্তু এদের প্রত্যেকের কাজের ধরন একে অপরের থেকে সম্পূর্ণ আলাদা।

বাবল সোর্ট (Bubble Sort) — প্রতিবেশীকে সোয়াপ করে উপরে ওঠা

বাবল সোর্ট পুরো অ্যারের ওপর দিয়ে পাস (pass) করে বা বারবার ঘোরে, আর পাশাপাশি থাকা জোড়াগুলো যদি ভুল ক্রমানুসারে থাকে, তবে তাদের সোয়াপ বা অদলবদল করে। প্রতিটি পাসের পরে, সবচেয়ে বড় অসাজানো উপাদানটি বুদবুদের মতো বা "বাবল (bubbled)" হয়ে একেবারে শেষের সঠিক স্থানে পৌঁছে যায়। একটি আর্লি-এক্সিট (early-exit) অপ্টিমাইজেশন দিয়ে (যদি কোনো পাসে একবারও সোয়াপ না হয়, তবে কাজ বন্ধ করে দেওয়া), আগে থেকেই সাজানো ইনপুটে এটি \(O(n)\) সময়ে কাজ করে। সবচেয়ে খারাপ ক্ষেত্রে (অর্থাৎ উল্টোভাবে সাজানো থাকলে), এটি \(O(n^2)\) বার সোয়াপ করে। এটি স্টেবল (stable) — সমান মানের উপাদানগুলো কখনোই সোয়াপ হয়ে একে অপরের স্থান পরিবর্তন করে না বা আগে পরে যায় না।

সিলেকশন সোর্ট (Selection Sort) — সবসময় সর্বনিম্ন মানটি খুঁজে নেওয়া

প্রতিটি i পজিশনের জন্য, সিলেকশন সোর্ট বাকি থাকা অসাজানো অংশটুকু স্ক্যান করে সবচেয়ে ছোট বা মিনিমাম (minimum) উপাদানটি খুঁজে বের করে, এবং এরপর সেটিকে i পজিশনের সাথে সোয়াপ করে। ইনপুট যেমনই হোক না কেন, এটি সবসময় ঠিক n(n−1)/2 বার তুলনা বা কম্পেয়ার করে — এতে আগে থেকে বের হয়ে আসার কোনো সুযোগ বা আর্লি-এক্সিট (early exit) নেই। এটি সর্বোচ্চ n−1 বার সোয়াপ করে, যা রাইট (write) অপারেশন ব্যয়বহুল বা মূল্যবান হলে বেশ কাজে দেয়। এটি স্টেবল নয় (not stable): সর্বনিম্ন মানটিকে তার সঠিক জায়গায় সোয়াপ করতে গিয়ে সমান মানের উপাদানগুলোকে ডিঙিয়ে যেতে পারে, ফলে তাদের নিজেদের আগের ক্রম পরিবর্তন হয়ে যেতে পারে।

ইনসার্শন সোর্ট (Insertion Sort) — ঠিক জায়গায় স্লাইড করা

ইনসার্শন সোর্ট বাঁ থেকে ডান দিকে একটি সাজানো সাব-অ্যারে (sorted subarray) তৈরি করে। প্রতিটি নতুন উপাদানের জন্য, এটি সাজানো অংশের উপাদানগুলোকে ডান দিকে সরাতে থাকে যতক্ষণ না ইনসার্ট বা প্রবেশ করানোর সঠিক জায়গাটি খুঁজে পায়। ইনপুটটি যদি প্রায়-সাজানো (nearly-sorted) হয়, তবে খুব অল্প জায়গাই সরাতে হয়: সব মিলিয়ে \(O(n)\)। কিন্তু যদি সব উল্টোভাবে সাজানো থাকে, তবে প্রতিটি উপাদানকেই তার আগের সব উপাদানের চেয়ে পেছনে সরতে হয়: যা \(O(n^2)\)। এটি স্টেবল এবং ইন-প্লেস (stable and in-place)।

ছোট সাইজের অ্যারের (n ≤ 16–32) জন্য ইনসার্শন সোর্টই প্রথম পছন্দের অ্যালগরিদম। পাইথনের টিম-সোর্ট (Timsort) এবং সি++ এর ইন্ট্রো-সোর্টের (Introsort) মতো প্রোডাকশন-লেভেলের সোর্ট ইঞ্জিনগুলো ছোট সাব-অ্যারের জন্য এই ইনসার্শন সোর্টেই ফিরে আসে বা নির্ভর করে, কারণ এর কনস্ট্যান্ট (constant) ফ্যাক্টর খুব ছোট এবং এর ক্যাশ-ফ্রেন্ডলি (cache-friendly) মেমরি অ্যাক্সেস প্যাটার্ন একে সেখানে সবচেয়ে দ্রুতগতির করে তোলে।

দ্রষ্টব্য: অল্প কিছু তাস সাজানোর ক্ষেত্রে ইনসার্শন সোর্টই হলো কার্ড-সোর্টিং চ্যাম্পিয়ন। যদি আপনার অ্যারে প্রায়-সাজানো বা আকারে বেশ ছোট হয়, তবে সাধারণ বা প্র্যাকটিক্যাল কাজে বিগ-ও (Big-O) এর কারণে নয় বরং ক্যাশ-ফ্রেন্ডলিনেস (cache friendliness) এবং সামান্য ওভারহেডের কারণে ইনসার্শন সোর্ট সহজেই মার্জ সোর্ট (merge sort) এবং কুইক সোর্টকে (quicksort) হারিয়ে দেবে।

তিনটি সোর্ট একসাথে (All Three Sorts — Side by Side)

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


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


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


data = [5, 3, 8, 1, 9, 2]
print("Bubble:   ", bubble_sort(data))
print("Selection:", selection_sort(data))
print("Insertion:", insertion_sort(data))
Output
Bubble:    [1, 2, 3, 5, 8, 9]
Selection: [1, 2, 3, 5, 8, 9]
Insertion: [1, 2, 3, 5, 8, 9]

Complexity

🫧 বাবল সোর্ট (Bubble Sort) — সেরা ক্ষেত্র বা বেস্ট কেস
আর্লি-এক্সিট (early-exit) সহ: একবার পাস করেই বুঝে যায়, কোনো সোয়াপের প্রয়োজন হয় না
লিনিয়ার (Linear) বা আগে থেকেই সাজানো \(O(n)\)
🫧 বাবল সোর্ট (Bubble Sort) — সবচেয়ে খারাপ বা ওয়ার্স্ট কেস
রিভার্স-সজ্জিত বা সম্পূর্ণ উল্টো ইনপুট — সর্বোচ্চ সংখ্যক সোয়াপ প্রয়োজন হয়
কোয়াড্রেটিক (Quadratic) \(O(n^2)\)
🏆 সিলেকশন সোর্ট (Selection Sort) — সব ক্ষেত্রে
সর্বদাই n(n−1)/2 সংখ্যকবার তুলনা বা কম্পারিজন করতে হয় — আগে থামার উপায় নেই। তবে সোয়াপ হয় খুব অল্প, সর্বোচ্চ n বার।
সর্বদাই কোয়াড্রেটিক (Quadratic) \(O(n^2)\)
🃏 ইনসার্শন সোর্ট (Insertion Sort) — সেরা ক্ষেত্র বা বেস্ট কেস
আগে থেকে সাজানো ইনপুটে প্রতি এলিমেন্টের জন্য মাত্র \(O(1)\) সংখ্যক শিফটিং প্রয়োজন হয়
লিনিয়ার (প্রায়-সজ্জিত বা nearly sorted) \(O(n)\)
🃏 ইনসার্শন সোর্ট (Insertion Sort) — সবচেয়ে খারাপ বা ওয়ার্স্ট কেস
প্রতিটি উপাদানকে তার আগের সবগুলোর পেছন দিয়ে শিফট হয়ে পার হতে হয়
কোয়াড্রেটিক (সম্পূর্ণ উল্টো সজ্জিত) \(O(n^2)\)

ছোট কুইজ

আপনি ১৫ টি প্রায়-সজ্জিত বা nearly-sorted পূর্ণসংখ্যাকে সাজাচ্ছেন। প্র্যাকটিক্যাল বা সাধারণ ব্যবহারে কোন অ্যালগরিদমটি জিতবে?

পড়া চালিয়ে যান