# Sorting ও Searching — কোন কাজ আগে কেন

**Sorting** তথ্যকে একটি নিয়মে সাজায়; **searching** সেই তথ্যের মধ্যে প্রয়োজনীয় অংশ খোঁজে। একবার ব্যবহার হলে সরল scan যথেষ্ট হতে পারে। একই data-তে অনেক query হলে sorting-এর এককালীন খরচ পরে বাঁচতে পারে।

## আগে যা পড়বেন

- [Array এবং index](../02-arrays-and-strings/concept.md): position আর value আলাদা।
- [দুটি sorted অংশ এক করা](../02-arrays-and-strings/problems/005-merge-sorted-array.md): কোন pointer এগোবে তা তুলনা ঠিক করে।
- [Lower bound-এর ধারণা](../01-math-based-programming-fundamentals/07-binary-search-on-answer/concept-notes.md): উত্তর খোঁজার interval কীভাবে ছোট হয়।

## একই input-এ তিনটি দৃষ্টিভঙ্গি

`[4, 1, 4, 2]` সাজিয়ে `[1, 2, 4, 4]` করতে হবে।

| পদ্ধতি | প্রতি ধাপে কী নিশ্চিত হয় | সময় | এই reference-এ অতিরিক্ত জায়গা |
| --- | --- | --- | --- |
| Bubble | একটি pass শেষে ডানের সবচেয়ে বড় মান স্থির | worst O(n²); আগে থেকেই sorted হলে O(n) | input copy-এর জন্য O(n) |
| Merge | ছোট sorted block জুড়ে বড় sorted block তৈরি | O(n log n) | O(n) |
| Three-way quicksort | ছোট / সমান / বড় partition আলাদা | সাধারণত O(n log n), worst O(n²) | O(n) |

Quicksort-এর সব implementation stable নয়। এখানে শেখানোর জন্য আলাদা partition list রাখা হয়েছে, তাই সমান key-র আগের ক্রম অক্ষত থাকে। In-place quicksort-এর space/stability-র দাবি এই implementation-এ প্রয়োগ করবেন না।

```mermaid
flowchart LR
    A[অগোছালো data] --> B[তুলনা করে সাজান]
    B --> C[Sorted keys]
    C --> D[Lower bound]
    C --> E[Upper bound]
    D --> F[সমান key-র পরিসর]
    E --> F
```

## Search-এ interval কেন জরুরি

`low` অন্তর্ভুক্ত, `high` বাদ: শুরু `[0, n)`। Lower bound-এ `values[mid] < target` হলে `low = mid + 1`; অন্যথায় `high = mid`। শেষে দুই সীমা একই index। Target না থাকলেও এটি তার ঢোকার জায়গা। Upper bound-এ শুধু তুলনা বদলায়: `<= target`।

Input sorted না হলে এই discard-এর যুক্তি থাকে না। এমন ক্ষেত্রে আগে sort করুন অথবা linear scan ব্যবহার করুন।

[চারটি problem](README.md) · [একসঙ্গে প্রয়োগের guided challenge](../guided-practice/sorting-searching.md)