কনটেন্টে যান

Guided challenge — পণ্যের catalogue ও দ্রুত query

আপনার দোকানের product list বারবার price দিয়ে খুঁজতে হয়। একই data-তে তিনটি sort-এর কাজের সংখ্যা তুলনা করুন; তারপর sorted price-এর উপর binary search চালিয়ে query-র উত্তর দিন। এটি নিজের শেখার project, কোনো coding platform বা Microsoft assignment-এর অনুলিপি নয়।

আগে কী পড়বেন

  1. Array ও index: কোন item কোথায় আছে বুঝুন।
  2. Bubble sort: pass-এর invariant লিখুন।
  3. Merge sort ও quicksort: ভাগ করা ও sorted অংশ জোড়া দেওয়া আলাদা কাজ।
  4. Boundary binary search: lower/upper bound-এর পার্থক্য।

Course মিল: Microsoft · M2-এর topic। Complexity তুলনা M5-এর performance-analysis অনুশীলনেও সাহায্য করে; এখানে Copilot বা .NET lab অনুকরণ করা হয়নি।

নির্দিষ্ট সমস্যা

products-এ (id, price) জোড়া, queries-এ খোঁজার price, আর একটি budget পাবেন। ফেরত দিতে হবে:

  • Price অনুযায়ী sorted product; সমান price-তে input-এর আগের ক্রম থাকবে।
  • প্রতিটি query-র জন্য সেই price-এর সব product ID। Query আবার এলেও আবার output দিন।
  • price <= budget এমন সব ID, sorted ক্রমে।
  • Bubble, merge ও quicksort-এর key comparison সংখ্যা। এটি runtime benchmark নয়।

সীমা: 0 <= products-এর সংখ্যা <= 200; ID nonempty ও unique string; price, query ও budget nonnegative integer (Boolean নয়)। Empty products/queries গ্রহণযোগ্য। মূল input বদলানো যাবে না। বেশি বড় input-এ bubble চালানো এই শিক্ষামূলক lab-এর লক্ষ্য নয়।

ছোট input থেকে পুরো ফল

Python
products = [("A", 40), ("B", 20), ("C", 40), ("D", 10)]
queries = [40, 25]
budget = 20
Price সাজলেও সমান price-এর ক্রম থাকে

  1. Input-এর price

    040↑ A
    120↑ B
    240↑ C
    310↑ D

  2. Sorted price

    010↑ D
    120↑ B
    চিহ্নিত ঘর: 240↑ A
    চিহ্নিত ঘর: 340↑ C

    A ও C দুটিই 40; A আগে ছিল, তাই এখনও আগে।

অংশ ফল
ordered [("D",10),("B",20),("A",40),("C",40)]
price 40 ["A","C"], কারণ boundary [2,4)
price 25 [], কারণ দুই boundary-ই 2
budget 20 ["D","B"], কারণ upper bound 2

Comparison counter-এ algorithm অনুযায়ী ভিন্ন সংখ্যা আসবে। নিচের tests-এ sorted input-এর bubble pass-এ ঠিক n−1 comparison হয় কি না আলাদা করে যাচাই করা আছে।

Milestone ১ — সরল baseline লিখুন

bubble_sort লিখুন। প্রতি pass শেষে ডানের স্থির অংশে সবচেয়ে বড়গুলো থাকবে।

Hint: এক pass-এ swap হয়নি মানে পুরো বর্তমান অংশ sorted। Checkpoint: reverse input, already-sorted input ও সব price সমান—তিনটিই পরীক্ষা করুন। সমান price-তে swap করলে স্থির ক্রম নষ্ট হতে পারে।

Milestone ২ — কম comparison-এর পদ্ধতি

Bottom-up merge_sort-এ width 1 → 2 → 4 করে এগোন। প্রতিটি merge-এ result-এর শেষ item সবচেয়ে ছোট অব্যবহৃত front থেকে এসেছে—এটাই invariant।

Three-way quick_sort-এ ছোট, সমান, বড় list বানান। Reference explicit task stack ব্যবহার করে; খারাপ partition হলেও Python recursion limit-এ আটকে যায় না।

Checkpoint: তিনটি result-ই Python-এর sorted(products, key=lambda p: p[1])-এর সঙ্গে মেলে। sorted test oracle; নিজের implementation-এর বদলে এটি ব্যবহার করবেন না। একই input অপরিবর্তিত থাকবে।

Milestone ৩ — exact price query

Sorted prices-এর lower_bound(target) এবং upper_bound(target) বের করুন। Result slice [left:right]-এ সব match; আলাদা করে linear scan করে শুরু খুঁজবেন না।

Invariant: lower bound-এর বাঁয়ে সব মান target-এর চেয়ে ছোট। Checkpoint: [1,2,2,2,5]-তে target 2 দিলে (1,4), 3 দিলে (4,4), empty list-এ (0,0)।

Milestone ৪ — budget ও পুরো report

Budget-এর upper bound পর্যন্ত prefix-ই affordable products। আগের তিন stage জুড়ে catalog_report বানান।

Checkpoint: worked input-এর report table মেলে, repeated query হারায় না, invalid ID/price-এ ValueError হয়। শেষে sorting comparison report থেকে কোন কাজ বারবার হচ্ছে তা ব্যাখ্যা করুন।

Reference solution ও unit test

সম্পূর্ণ runnable solution · আটটি test group

Repository root থেকে:

Bash
python -m unittest discover -s practice -p "test_sorting_lab.py" -v
Python
from practice.sorting_lab import catalog_report

result = catalog_report([("A", 40), ("B", 20), ("C", 40), ("D", 10)], [40, 25], 20)
assert result["affordable"] == ["D", "B"]
assert result["matches"][0]["ids"] == ["A", "C"]

নিজে করতে চাইলে solution file-এর function body লিখে একই tests চালান। Reference code আগে পড়ে ফেললে নতুন input নিজে তৈরি করে expected output হাতে লিখুন।

খরচ, coverage ও বাকি অনুশীলন

অংশ কী শিখছেন এই challenge-এ নেই
Sort তুলনা stability, invariant, comparison, early exit external sorting, counting/radix sort
Quicksort three-way partition, explicit stack in-place partition-এর memory guarantee
Boundary query duplicate, absent key, half-open interval binary search on a general feasibility predicate
Integration sort একবার, query বারবার, validation concurrent database index বা database engine

এই lab তিনটি sort-ই চালায়, তাই মোট worst time O(n² + q log n + K), যেখানে K হলো সব query-তে ফেরত দেওয়া ID-এর মোট সংখ্যা। শুধু merge sort রেখে production-style variant করলে O(n log n + q log n + K)। Input বাদে sorting scratch O(n), returned query data O(q + K)।

একটি short counterexample লিখুন: unsorted price-এ binary search কেন ভুল হতে পারে? তারপর পুরো problem map-এ ফিরে remaining exercises করুন।