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

লিনিয়ার-টাইম সর্টিং (Linear-Time Sorting)

তুলনা ছাড়াই সর্ট করুন — \(O(n \log n)\) এর দেয়াল ভেঙে ফেলার কৌশল
counting sort:\(O(n + k)\)radix sort:\(O(d \times (n + k))\)bucket sort:গড়ে \(O(n)\)requirement:একটি নির্দিষ্ট সীমা বা রেঞ্জের মধ্যে থাকা পূর্ণসংখ্যা

কল্পনা করুন আপনি এক বান্ডিল চিঠি পোস্ট অফিসের বক্স বা ড্রয়ারে সাজাচ্ছেন। আপনাকে একটি চিঠির সাথে অন্য চিঠির তুলনা করার দরকার নেই — আপনি শুধু প্রতিটি চিঠির নম্বর দেখে তাকে নির্দিষ্ট ড্রয়ারে রেখে দিচ্ছেন। এটিই লিনিয়ার-টাইম সর্টিংয়ের মূল ধারণা: উপাদানগুলোর একে অপরের সাথে তুলনা করার বদলে আমরা তাদের সম্পর্কে থাকা বাড়তি তথ্য (যেমন রেঞ্জ বা সীমা) কাজে লাগাই।

সাধারণ মেথডগুলো (যেমন কুইক সর্ট বা মার্জ সর্ট) \(O(n \log n)\)-এর নিচে নামতে পারে না কারণ তাদের প্রতিটি তুলনা মাত্র ১ বিট তথ্য দেয়। লিনিয়ার সর্টগুলো এই সীমা অতিক্রম করতে পারে কারণ তারা জানে ইনপুটগুলোর মান ঠিক কোন সীমা বা ধরনের মধ্যে থাকবে।

কাউন্টিং সর্ট (Counting Sort) — সহজ ধারণা

যদি আপনার কাছে ০ থেকে k সীমার মধ্যে কিছু পূর্ণসংখ্যা থাকে, তবে কাউন্টিং সর্ট এভাবে কাজ করে: (১) প্রতিটি সংখ্যা কতবার আছে তা গুনে ফেলুন। (২) এই সংখ্যাগুলোকে নিয়ে শুরু হওয়ার পজিশন বা ইনডেক্স ঠিক করুন (যা প্রিফিক্স সাম এর মাধ্যমে করা হয়)। (৩) ইনপুট থেকে প্রতিটি সংখ্যা নিয়ে সরাসরী তার জন্য নির্ধারিত জায়গায় বসিয়ে দিন।

সময়: \(O(n + k)\)। মেমরি: \(O(n + k)\)। এটি একটি স্টেবল (Stable) সর্ট যদি আপনি আউটপুট বসানোর সময় পিছন থেকে কাজ করেন (যা রেডিক্স সর্টের জন্য খুব জরুরি)। যদি k-এর মান n-এর কাছাকাছি হয়, তবে এটি \(O(n)\) বা লিনিয়ার সময়ে কাজ শেষ করে। কিন্তু যদি k অনেক বড় হয় (যেমন ১ থেকে ১ কোটির রেঞ্জ), তবে এটি অনেক বেশি মেমরি অপচয় করবে।

রেডিক্স সর্ট (Radix Sort) — অঙ্ক ধরে সর্ট করা

রেডিক্স সর্ট অনেক বড় ইনটিজার হ্যান্ডেল করতে পারে প্রতিটি অঙ্কের (Digit) ওপর সর্ট করার মাধ্যমে। এটি মূলত একক ঘর থেকে শুরু করে বাম দিকে (LSD) এগোয় এবং প্রতিটি ধাপে একটি স্টেবল সর্ট (যেমন কাউন্টিং সর্ট) ব্যবহার করে। সবগুলো অঙ্ক শেষ হওয়ার পর পুরো অ্যারেটি সর্ট হয়ে যায়।

কেন একক ঘর থেকে শুরু করা হয়? কারণ 'স্ট্যাবিলিটি' পূর্ববর্তী ধাপের পরিশ্রমকে ধরে রাখে। একক ঘর সর্ট করার পর যখন দশকের ঘর সর্ট করা হয়, তখন একই দশকওয়ালা সংখ্যাগুলো তাদের এককের ঘরের ক্রম ঠিক থাকে — এভাবে প্রতিটি ধাপ শেষে নির্ভুলভাবে সর্টিং এগিয়ে চলে।

আপনি যদি ৩২-বিটের ইনটিজার ব্যবহার করেন ২৫৬ বেস (Base) ধরে, তবে মাত্র ৪টি ধাপে আপনি \(O(n)\) সময়ে সর্ট করতে পারবেন, যা বড় ডেটার জন্য \(O(n \log n)\) এর চেয়ে দ্রুত।

বাকেট সর্ট (Bucket Sort) — ভাগ করে বণ্টন করা

বাকেট সর্ট পুরো রেঞ্জকে সমান ভাগে কয়েকটি 'বাকেট' বা বালতিতে ভাগ করে দেয়। প্রতিটি সংখ্যাকে তার নির্দিষ্ট বালতিতে ফেলে দেওয়া হয়, এরপর প্রতিটি বালতিকে ছোট কোনো সর্টিং মেথড (যেমন ইনসারশন সর্ট) দিয়ে সর্ট করা হয়। সবশেষে বালতিগুলোকে ক্রমানুসারে সাজালেই পূর্ণ সর্ট পাওয়া যায়।

শর্ত: যদি ইনপুটগুলো ইউনিফর্মলি ডিস্ট্রিবিউটেড (Uniformly distributed) বা সুষমভাবে ছড়ানো থাকে, তবে প্রতিটি বালতিতে গড়ে ১-২টি উপাদান থাকে, ফলে পুরো কাজ \(O(n)\) সময়ে শেষ হয়। তবে যদি সব উপাদান কোনো একটি নির্দিষ্ট বালতিতে জমা হয়, তবে এটি \(O(n^2)\) জটিলতাও তৈরি করতে পারে।

দ্রষ্টব্য: লিনিয়ার সর্টগুলো কিন্তু বিজ্ঞানের কোনো সাধারণ নিয়ম ভাঙে না — এরা শুধু সেই বাড়তি তথ্যটি ব্যবহার করে যা অন্যান্য সর্টিং ফেলে দেয়। যেকোনো কম্পারিজন সর্ট শুধু জিজ্ঞেস করে 'A কি B-এর চেয়ে ছোট?' কিন্তু লিনিয়ার সর্ট জিজ্ঞেস করে 'A এর প্রকৃত মান কত?' — আর এই বাড়তি তথ্যটুকুই বাড়তি গতি এনে দেয়।

কাউন্টিং এবং রেডিক্স সর্ট — কোড উদাহরণ

def counting_sort(arr, k=None):
    # k is max input value + 1
    if not arr: return arr
    k = k or (max(arr) + 1)
    count = [0] * k
    for x in arr:
        count[x] += 1
    
    # Compute positions from prefix sums
    for i in range(1, k):
        count[i] += count[i - 1]
    
    out = [0] * len(arr)
    # Loop backwards to preserve stability
    for x in reversed(arr):
        count[x] -= 1
        out[count[x]] = x
    return out


def radix_sort(arr):
    if not arr: return arr
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        arr = counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr


def counting_sort_by_digit(arr, exp):
    count = [0] * 10
    for x in arr: count[(x // exp) % 10] += 1
    for i in range(1, 10): count[i] += count[i-1]
    out = [0] * len(arr)
    for x in reversed(arr):
        d = (x // exp) % 10
        count[d] -= 1
        out[count[d]] = x
    return out


# Test
print(counting_sort([4, 2, 2, 8, 3, 3, 1]))
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
Output
[1, 2, 2, 3, 3, 4, 8]
[2, 24, 45, 66, 75, 90, 170, 802]

Complexity

🗂️ কাউন্টিং সর্ট
k যখন n-এর কাছাকাছি থাকে তখন এটি সেরা; k অনেক বড় হলে মেমরি অপচয় হয়
ডেটা এবং সীমার (k) যোগফলের সমান \(O(n + k)\)
🔢 রেডিক্স সর্ট
d = ডিজিট সংখ্যা, k = বেস। ৩২-বিট ইনটিজারের জন্য এটি গড়ে \(O(n)\)
ফিক্সড-সাইজ ইনটিজারের জন্য লিনিয়ার \(O(d \times (n + k))\)
🪣 বাকেট সর্ট — এভারেজ
সুষম বণ্টন থাকলে প্রতিটি বাকেটে মাত্র \(O(1)\) উপাদান থাকে
সুষম বণ্টনের ক্ষেত্রে লিনিয়ার \(O(n)\)
🪣 বাকেট সর্ট — ওর্স্ট কেস
ডেটা ডিস্ট্রিবিউশন খারাপ হলে এটি অনেক সময় নিতে পারে
সব ডেটা এক বালতিতে পড়লে কোয়াড্রাটিক \(O(n^2)\)

ছোট কুইজ

কাউন্টিং সর্ট কীভাবে সর্টিংয়ের সর্বনিম্ন সীমা \(O(n \log n)\) অতিক্রম করতে পারে?

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