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

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

একটি পিভট (pivot) বেছে নিন, জনতাকে ভাগ করুন — ছোটরা বাঁয়ে, বড়রা ডানে
average case:\(O(n \log n)\)worst case:\(O(n^2)\) — খারাপ পিভটspace:\(O(\log n)\) স্ট্যাকin-place:হ্যাঁ

কল্পনা করুন আপনি একদল মানুষকে উচ্চতা অনুযায়ী সাজাচ্ছেন। আপনি একজনকে বেছে নিলেন — সেই হলো পিভট (pivot) — এবং অন্যদের বললেন, যারা তার চেয়ে খাটো তারা যেন বাঁয়ে গিয়ে দাঁড়ায়, আর যারা লম্বা তারা ডানে। এখন পিভট ঠিক এমন এক জায়গায় পৌঁছে গেল, যেটি সাজানোর পর তার আসল অবস্থান হবে। এরপর বাঁ দিকের আর ডান দিকের দলের ওপর আলাদাভাবে একই নিয়মের পুনরাবৃত্তি করুন। কুইক সর্টের মূল কাজ এটিই: পিভট বেছে নেওয়া, ভাগ বা পার্টিশন (partition) করা, এবং রিকার্শন (recursion) প্রয়োগ করা।

বাস্তবে এটি খুব দ্রুত কাজ করে, কারণ এর পার্টিশন করার পদ্ধতিটি হলো কন্টিনিউয়াস মেমরিতে (contiguous memory) দ্রুত স্ক্যান করা (ফলে এটি ক্যাশ মেমরির জন্য খুব ভালো বা cache-friendly!), এবং গড়ে পিভটটি একদম মাঝ বরাবর পড়ে যা সুষম রিকার্শন নিশ্চিত করে।

পার্টিশন বা ভাগ করার ধাপ (The Partition Step)

লোমুতোর পার্টিশন (Lomuto partition) (বোঝা সহজ): অ্যারের একেবারে শেষের উপাদানটিকে পিভট হিসেবে বেছে নিন। বাঁ দিক থেকে একটি পয়েন্টার i কে এগিয়ে নিতে থাকুন; যখনই আপনি এমন কোনো উপাদান পাবেন যা পিভটের চেয়ে ছোট বা সমান (≤), সেটিকে i অবস্থানের উপাদানের সাথে অদলবদল (swap) করুন এবং i কে এক ধাপ এগিয়ে দিন। একদম শেষে, পিভটকে i অবস্থানে নিয়ে আসুন। এটির কোড লেখা সহজ, তবে এতে সোয়্যাপ বা অদলবদলের সংখ্যা একটু বেশি হয়।

হোয়ারের পার্টিশন (Hoare partition) (বাস্তবে বেশি দ্রুত): দুটি পয়েন্টার দুই মেরু বা প্রান্ত থেকে শুরু হয়। বাঁ দিকের পয়েন্টারটি ডানে এগোতে থাকে যতক্ষণ না এটি পিভটের সমান বা ছোট (≤) উপাদান পায়; ডান দিকের পয়েন্টার বাঁয়ে এগোয় যতক্ষণ না এটি পিভটের সমান বা বড় (≥) উপাদান পায়। যখন দুটি পয়েন্টারই আটকে যায়, তখন তাদের উপাদানগুলো একে অপরের সাথে বদল (swap) করে আবার চলতে থাকে, যতক্ষণ না পয়েন্টার দুটি একে অপরকে পার হয়ে যায়। র্যান্ডম ইনপুটে এটি লোমুতোর চেয়ে প্রায় ৩ গুণ কম সোয়্যাপ করে।

পিভট বেছে নেওয়া — সবকিছু এর ওপর নির্ভর করে

প্রথম বা শেষ উপাদান: আগে থেকেই সাজানো থাকলে (sorted) বা উল্টো দিক থেকে সাজানো থাকলে (reverse-sorted) এটি চরম মাত্রায় বিপর্যয় ডেকে আনে। এর ফলে প্রতিটি পার্টিশনে এক দিক পুরোপুরি ফাঁকা থেকে যায় → রিকার্শনের গভীরতা হয় \(O(n^2)\)।

র্যান্ডম পিভট (Random pivot): যেকোনো একটি র্যান্ডম ইনডেক্স বেছে নিন এবং পার্টিশন করার আগেই সেটিকে সঠিক অবস্থানে নিয়ে আসুন। র্যান্ডম বা দৈবচয়ন পদ্ধতির কারণে \(O(n^2)\)-এর মতো সবচেয়ে খারাপ বা ওয়ার্স্ট-কেস (worst-case) ঘটার সম্ভাবনা প্রায় অসম্ভব হয়ে যায় — ধারাবাহিকভাবে সবচেয়ে বাজে পিভট পড়ার সম্ভাবনা হলো (2/n)^n।

মিডিয়ান-অফ-থ্রি (Median-of-three): প্রথম, মধ্যবর্তী, এবং শেষ উপাদানটির দিকে লক্ষ্য রাখুন; এবং এদের মধ্যে যেটি মাঝামাঝি (median) সেটিকে পিভট হিসেবে বেছে নিন। এর খরচ কম, এটি সাজানো ইনপুটের সমস্যার সমাধান করে, এবং কোনো র্যান্ডম নম্বর তৈরির দরকার হয় না।

গড়ে (Average Case) \(O(n \log n)\) — এটি যেভাবে কাজ করে

র্যান্ডম পিভট ব্যবহার করলে, একটি পিভট যা মানের দিক থেকে মাঝের ৫০% অংশে পড়ে (যেটি পড়ার সম্ভাবনা ১/২), সেটি কখনো ২৫%-৭৫% এর চেয়ে বিভাজনে খারাপ কিছু করবে না। ফলে, এর রিকার্শন ডেপথ বা গভীরতা গড়ের ক্ষেত্রে (in expectation) \(O(\log n)\) থাকবে। আরো নির্দিষ্ট করে বললে, এতে প্রত্যাশিত কম্প্যারিজনের পরিমাণ প্রায় 2n ln n ≈ 1.39 n \(\log_2\)n — যা মার্জ সর্টের n \(\log_2\)n এর চেয়ে প্রায় ৩৯% বেশি, তবে এর ক্যাশ বিহেভিয়ার মার্জ সর্টের চেয়ে অনেক ভালো।

ইন্ট্রোসর্ট (Introsort) — বাস্তব জগতে উভয়ের সেরা রূপ

সব নামী স্ট্যান্ডার্ড লাইব্রেরিগুলোই ইন্ট্রোসর্ট (Introsort) ব্যবহার করে: শুরুতে কুইক সর্ট দিয়েই কাজ শুরু করা হয়, তবে এটি রিকার্শনের গভীরতা খেয়াল রাখে। যদি গভীরতা 2·log n ছাড়িয়ে যায়, তবে এটি স্বয়ংক্রিয়ভাবে হিপসর্টে (heapsort) চলে যায়। এর ফলে কুইক সর্টের চমৎকার গড় পারফরম্যান্স বজায় থাকার পাশাপাশি ওয়ার্স্ট কেসও \(O(n \log n)\) এ সুরক্ষিত থাকে। ছোট সাইজের অ্যারের জন্য (সাধারণত n ≤ ~32), এগুলো ইনসার্শন সর্টে (insertion sort) চলে যায়। C++ এর std::sort, জাভার প্রিমিটিভ ডাটা টাইপের জন্য Arrays.sort এবং রাস্টের (Rust) slice::sort_unstable — সবই ইন্ট্রোসর্ট ব্যবহার করে থাকে।

দ্রষ্টব্য: কুইক সর্ট (Quicksort) বনাম মার্জ সর্ট (Merge sort): বাস্তবে কুইক সর্টই জেতে, কারণ পার্টিশন করার সময় এটি সিরিয়ালি মেমরি স্ক্যান করে (যা ক্যাশ-বান্ধব বা cache-friendly) এবং এর কোনো বাড়তি অ্যারের দরকার হয় না। তবে তাত্ত্বিকভাবে মার্জ সর্ট এগিয়ে থাকে: এটি স্টেবল (stable), সব ক্ষেত্রে \(O(n \log n)\) নিশ্চিত করে এবং এর স্পেস কমপ্লেক্সিটি \(O(n)\)। তবে বাস্তবে ইন-মেমরি সর্টিংয়ের (in-memory sorting) ক্ষেত্রে র্যান্ডমাইজড কুইক সর্টই ডিফল্ট বা প্রথম পছন্দ।

কুইক সর্ট — লোমুতোর পার্টিশন (Lomuto Partition)

import random


def quicksort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo < hi:
        p = partition(arr, lo, hi)
        quicksort(arr, lo, p - 1)
        quicksort(arr, p + 1, hi)


def partition(arr, lo, hi):
    # Random pivot for O(n²) worst-case avoidance
    r = random.randint(lo, hi)
    arr[r], arr[hi] = arr[hi], arr[r]
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1


data = [10, 7, 8, 9, 1, 5]
quicksort(data)
print(data)
Output
[1, 5, 7, 8, 9, 10]

Complexity

🚀 গড়ের ক্ষেত্রে (Average case)
র্যান্ডম পিভট ব্যবহার করলে প্রত্যাশিত — মার্জ সর্টের তুলনায় ~১.৩৯ গুণ বেশি তুলনা করলেও ক্যাশ বিহেভিয়ার (cache behavior) এর চেয়ে বেশ ভালো
লিনিয়ারিদমিক (Linearithmic) — বাস্তবে খুব দ্রুত \(O(n \log n)\)
💀 ওয়ার্স্ট কেস (Worst case)
আগে থেকেই সাজানো (sorted) বা উল্টো সাজানো ইনপুটে প্রথম/শেষ পিভট ব্যবহার করলে এমন হয় — এটি এড়াতে র্যান্ডম পিভট ব্যবহার করুন
কোয়াড্রেটিক (Quadratic) — প্রতিটি পিভটই যদি চরম মানের হয় \(O(n^2)\)
📦 মেমরি (স্ট্যাক/stack)
ইন-প্লেস (In-place) — কেবল রিকার্শন স্ট্যাক লাগে; টেল রিকার্শন অপ্টিমাইজেশন (tail recursion optimization) ছাড়া ওয়ার্স্ট কেসে \(O(n)\) লাগতে পারে
গড়ে লগারিদমিক (Logarithmic) \(O(\log n)\)
⚡ পার্টিশন (Partition) ধাপ
এটি পর্যায়ক্রমিক মেমরি স্ক্যান (Sequential memory scan) করে — তাই চমৎকার ক্যাশ পারফরম্যান্স দেয়
বর্তমান রেঞ্জের (range) লিনিয়ার স্ক্যান \(O(n)\)

ছোট কুইজ

শেষের উপাদানটিকে পিভট হিসেবে ব্যবহার করলে কোন ধরনের ইনপুট প্যাটার্নটি কুইক সর্টের \(O(n^2)\) ওয়ার্স্ট কেস ট্রিগার করে?

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