Sorting algorithm: insertion, merge ও quick sort, সময়সহ

Sorting হলো ক্লাসিক interview বিষয়, আর এটি এমন ধারণা শেখায় যা সব জায়গায় পাবেন: ভাগ করে জয় (divide and conquer), সময় ও মেমরির আদান-প্রদান, এবং "stable" মানে কী। বাস্তব প্রজেক্টে প্রায় সবসময় built-in sort ডাকবেন, কিন্তু algorithm বুঝলে জানা যায় এটি কেন দ্রুত এবং কী আচরণ আশা করবেন। নিচের কোড ও সময় প্রকাশের আগে Python 3-এ চালানো হয়েছে।

তিনটি algorithm

Insertion sort। বাঁ দিকের অংশ সাজানো রাখুন। পরের item নিয়ে বাঁয়ে সরাতে থাকুন যতক্ষণ না ঠিক জায়গা মেলে, হাতে তাস সাজানোর মতো। সরল, সবচেয়ে খারাপ ক্ষেত্রে O(n²), কিন্তু data প্রায় সাজানো থাকলে O(n)-এর কাছাকাছি।

Merge sort। তালিকা অর্ধেক করুন, প্রতিটি অর্ধেক (পুনরাবৃত্তিতে) সাজান, তারপর দুটি সাজানো অর্ধেক মেলান: বারবার সামনের ছোট item নিয়ে। সবসময় O(n log n), কিন্তু O(n) অতিরিক্ত মেমরি লাগে।

Quick sort। একটি pivot বাছুন, ছোটগুলো একপাশে ও বড়গুলো অন্য পাশে সরান, তারপর দুই পাশ সাজান। গড়ে O(n log n), জায়গাতেই (in place), বাস্তবে সাধারণত খুব দ্রুত। Pivot ক্রমাগত খারাপ হলে সবচেয়ে খারাপ ক্ষেত্র O(n²), যেমন আগে থেকে সাজানো data-তে সবসময় প্রথম item নেওয়া। এলোমেলো pivot তা অসম্ভাব্য করে।

একটি চালানো যায় এমন উদাহরণ

sorting.py নামে সংরক্ষণ করুন:

import random
import time


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


def merge_sort(a):
    if len(a) <= 1:
        return list(a)
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= keeps equal items in original order (stable)
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]


def quick_sort(a):
    a = list(a)

    def go(lo, hi):
        while lo < hi:
            p = a[random.randint(lo, hi)]  # random pivot avoids the sorted-input trap
            i, j = lo, hi
            while i <= j:
                while a[i] < p: i += 1
                while a[j] > p: j -= 1
                if i <= j:
                    a[i], a[j] = a[j], a[i]
                    i += 1; j -= 1
            # recurse into the smaller side, loop on the larger: stack stays O(log n)
            if j - lo < hi - i:
                go(lo, j); lo = i
            else:
                go(i, hi); hi = j

    go(0, len(a) - 1)
    return a


def timed(fn, data):
    t = time.perf_counter()
    fn(data)
    return (time.perf_counter() - t) * 1000


if __name__ == "__main__":
    random.seed(1)
    n = 3000
    inputs = {
        "random": [random.randint(0, 10**6) for _ in range(n)],
        "already sorted": list(range(n)),
        "reversed": list(range(n, 0, -1)),
    }
    print(f"n = {n}, milliseconds (one run each)")
    print(f"{'input':<16}{'insertion':>11}{'merge':>9}{'quick':>9}{'sorted()':>10}")
    for name, data in inputs.items():
        row = [timed(f, data) for f in (insertion_sort, merge_sort, quick_sort, sorted)]
        print(f"{name:<16}{row[0]:>11.2f}{row[1]:>9.2f}{row[2]:>9.2f}{row[3]:>10.2f}")

    print()
    people = [("Asha", 30), ("Bijoy", 25), ("Chitra", 30), ("Dipu", 25)]
    print("stable by age  :", sorted(people, key=lambda p: p[1]))

python3 sorting.py-এর ফল (৩,০০০ সংখ্যা, একবার করে; সঠিক সময় মেশিনভেদে বদলায়):

n = 3000, milliseconds (one run each)
input             insertion    merge    quick  sorted()
random               576.29    14.41     9.21      0.79
already sorted         0.61     9.24     6.39      0.05
reversed             929.60    11.50     7.43      0.08

stable by age  : [('Bijoy', 25), ('Dipu', 25), ('Asha', 30), ('Chitra', 30)]

সময় পড়া

• Random data: insertion sort নিল ৫৭৬ ms, merge sort প্রায় ১৪ ms, quick sort প্রায় ৯ ms। মাত্র ৩,০০০ item-এই O(n²) আনুমানিক ৪০ থেকে ৬০ গুণ ধীর। ৩,০০,০০০ item-এ ফারাক অসহনীয় হতো।
• আগে থেকে সাজানো: নিজে লেখা তিনটির মধ্যে insertion sort জেতে (০.৬১ ms), কারণ প্রতিটি item একবার দেখে, কিছু সরায় না। এই কারণেই গুরুত্বপূর্ণ sorting routine-এর ভেতরে ছোট বা প্রায়-সাজানো অংশে insertion sort ব্যবহার হয়।
• উল্টো সাজানো: insertion sort-এর সবচেয়ে খারাপ ক্ষেত্র (৯৩০ ms): প্রতিটি item একেবারে সামনে পর্যন্ত সরে।
• sorted() সবগুলোর চেয়ে দ্রুত, যদিও আমাদের কোড সাধারণ Python। এটি জাদু নয়: এটি C-তে লেখা এবং এমন algorithm ব্যবহার করে যা বিদ্যমান ক্রমকে কাজে লাগায়।

"Stable" মানে কী

Sort stable হয় যদি সমান তুলনার item-গুলো তাদের মূল আপেক্ষিক ক্রম রাখে। শেষ লাইন দেখুন: বয়স অনুযায়ী সাজাতে Asha, Chitra-র আগে এবং Bijoy, Dipu-র আগে থেকেছে, ঠিক input-এর মতো। একটি key দিয়ে সাজিয়ে আরেকটি দিয়ে সাজালে (যেমন শহর, তারপর বয়স) এটি গুরুত্বপূর্ণ। Merge sort stable (merge ধাপের <= তা নিশ্চিত করে)। সাধারণ in-place quick sort stable নয়। Python-এর built-in sort stable, যা নথিভুক্ত আচরণ, নির্ভর করা যায়।

Python আসলে কী ব্যবহার করে

sorted() ও list.sort() Timsort ব্যবহার করে: merge sort ও insertion sort-এর সংকর, যা data-তে আগে থেকে সাজানো অংশ (run) খুঁজে মেলায়। সবচেয়ে খারাপ ক্ষেত্রে O(n log n), প্রায়-সাজানো data-তে O(n)-এর কাছাকাছি, তাই "আগে থেকে সাজানো" সারি এত দ্রুত। JavaScript-এর Array.prototype.sort ES2019 থেকে stable হতে বাধ্য; algorithm engine-নির্ভর।

Test

test_sorting.py নামে সংরক্ষণ করুন:

import random
import unittest

from sorting import insertion_sort, merge_sort, quick_sort

ALGOS = (insertion_sort, merge_sort, quick_sort)


class SortTests(unittest.TestCase):
    def test_matches_builtin_on_random_data(self):
        rnd = random.Random(7)
        for _ in range(200):
            data = [rnd.randint(-50, 50) for _ in range(rnd.randint(0, 60))]
            for f in ALGOS:
                self.assertEqual(f(data), sorted(data), f.__name__)

    def test_edge_cases(self):
        for f in ALGOS:
            self.assertEqual(f([]), [])
            self.assertEqual(f([1]), [1])
            self.assertEqual(f([2, 2, 2]), [2, 2, 2])
            self.assertEqual(f(list(range(1000, 0, -1))), list(range(1, 1001)))

    def test_input_not_modified(self):
        data = [3, 1, 2]
        for f in ALGOS:
            f(data)
            self.assertEqual(data, [3, 1, 2])


if __name__ == "__main__":
    unittest.main()

$ python3 -m unittest -v
Ran 3 tests in 0.162s

OK

আমরা প্রতিটি algorithm-কে ২০০টি random তালিকায় (খালি ও অনেক ডুপ্লিকেটসহ) sorted()-এর সঙ্গে মেলাই, edge case দেখি, এবং input তালিকা অপরিবর্তিত থাকে কি না যাচাই করি। নতুন algorithm-কে random data-তে বিশ্বস্ত একটির সঙ্গে মেলানো খুবই কার্যকর test অভ্যাস।

কখন কোনটি?

• আসল কোডে: built-in sort ব্যবহার করুন। নিজে লিখবেন না।
• Interview বা শেখা: merge sort (পরিষ্কার, নিশ্চিত O(n log n), stable) ও quick sort (গড় ক্ষেত্রে সেরা, in place) জানুন এবং সবচেয়ে খারাপ ক্ষেত্র ব্যাখ্যা করতে পারুন।
• ছোট বা প্রায়-সাজানো data: insertion sort ঠিক আছে, তাই লাইব্রেরি ছোট অংশে এটি ব্যবহার করে।
• সীমিত মেমরি, stability লাগে না: quick sort বা heap sort-এর মতো in-place sort।
• ছোট পরিসরের পূর্ণসংখ্যা: counting বা radix sort O(n log n)-কে হারাতে পারে, কারণ এরা item তুলনা করে না।

একটি পরিচিত তথ্য: যে sort শুধু তুলনা করে কাজ করে, সবচেয়ে খারাপ ক্ষেত্রে তার অন্তত প্রায় n log n তুলনা লাগে। তাই সাধারণ sorting-এর লক্ষ্য O(n log n)।

সাধারণ ভুল

• খারাপ pivot বাছা, যেমন সবসময় প্রথম item, ফলে sorted input-এ O(n²)।
• একাধিক key দিয়ে সাজানোর সময় stability ভুলে যাওয়া।
• একবারের বদলে loop-এর ভেতরে বারবার sort করা, বা শুধু সর্বনিম্ন খুঁজতে sort করা (min ব্যবহার করুন, O(n))।
• Caller আশা করে না তবু input তালিকা বদলে ফেলা।
• Library থাকতে প্রোডাকশনে নিজস্ব sort লেখা।
• অসঙ্গত তুলনা ফাংশন ব্যবহার, যা ভুল ফল বা error দিতে পারে।

মূল কথা: Insertion sort সরল এবং ছোট বা প্রায়-সাজানো data-তে ভালো, merge sort নিরাপদ O(n log n) ও stable, ভালো pivot থাকলে quick sort গড়ে দ্রুত। বাস্তব প্রজেক্টে built-in sort ব্যবহার করুন, আর এই algorithm-গুলো দিয়ে বুঝুন এটি কেন তেমন আচরণ করে।

---

Interview প্রস্তুতি ও DSA সিরিজ, পর্ব ৩ (আরও algorithm): 1 নম্বর (মোট 5)।