# Quicksort — pivot দিয়ে তিন ভাগ

<div class="problem-source" markdown="1">

- **Original source:** এই repository-র নিজস্ব অনুশীলন
- **Topic:** sorting / searching
- **Difficulty:** Medium
- **Pattern:** partition / explicit stack
- **Course:** Microsoft · Module 2-এর topic অনুশীলন; official assignment নয়

</div>

## প্রশ্ন ও উদাহরণ {#problem}

একটি integer list দেওয়া আছে। মূল list না বদলে ছোট থেকে বড় ক্রমে নতুন list ফেরত দিন; শেখার জন্য নির্দিষ্ট algorithm-টি নিজে লিখুন। Empty input ও duplicate থাকতে পারে। হাতে trace করার সময় সর্বোচ্চ 8টি মান নিন; lab report-এ সর্বোচ্চ 200টি product।

- Input: `[4, 1, 4, 2]`
- Output: `[1, 2, 4, 4]`

## ভিত্তির ধারণা {#idea}

আগে পড়ুন: [sorting/searching-এর ধারণা](../concept.md), [array ও index](../../02-arrays-and-strings/concept.md)। এরপর `partition / explicit stack`-এর কাজটি নিজের ভাষায় বলুন।

মাঝের element-কে pivot নিন। অন্য মানগুলো pivot-এর চেয়ে ছোট, সমান ও বড়—তিনটি list-এ রাখুন। ছোট ও বড় অংশ আবার ভাগ করুন। সমান অংশ আর sort করতে হবে না।

## ধাপে ধাপে সমাধান {#walkthrough}

| ধাপ | ছোট | সমান | বড় |
| --- | --- | --- | --- |
| pivot 4 | `[1,2]` | `[4,4]` | `[]` |
| ছোট অংশে pivot 2 | `[1]` | `[2]` | `[]` |
| যোগ করার ক্রম | `[1]` + `[2]` | + `[4,4]` | = `[1,2,4,4]` |

**Checkpoint:** পরের তুলনা code চালানোর আগে নিজে লিখুন। কোন অংশ আর বদলাবে না, সেটি চিহ্নিত করুন।

**ইঙ্গিত:** Explicit task stack LIFO: বড়, সমান, ছোট—এই উল্টো ক্রমে push করলে ছোট অংশ আগে process হবে। এই extra-list variant stable; সাধারণ in-place quicksort stable হওয়ার নিশ্চয়তা নেই।

## কোড ও ব্যাখ্যা {#code}

সম্পূর্ণ implementation আছে [sorting_lab.py](../../practice/sorting_lab.py)-এ। Repository root থেকে নিচের ছোট example চালানো যায়:

```python
from practice.sorting_lab import quick_sort

print(quick_sort([4, 1, 4, 2]))
```

প্রথমে reference না দেখে function লিখুন। পরে loop boundary ও কোন অবস্থায় pointer বাড়ছে তা reference-এর সঙ্গে মিলিয়ে দেখুন।

## খরচ ও সাধারণ ভুল {#cost}

সাধারণত O(n log n), খারাপ partition-এ O(n²); এই explicit-stack/list variant-এ O(n) extra space।

Empty list, একই মান বারবার, আগে থেকেই sorted, উল্টো sorted এবং একটিমাত্র element পরীক্ষা করুন। Input list ভুল করে বদলে যাচ্ছে কি না তাও দেখুন।

## শেখা ও পরের অনুশীলন {#practice}

[পরীক্ষাগুলো](../../practice/test_sorting_lab.py) দিয়ে output, stability ও edge case মিলিয়ে নিন:

```bash
python -m unittest discover -s practice -p "test_sorting_lab.py" -v
```

তারপর [পণ্যের catalogue guided challenge](../../guided-practice/sorting-searching.md)-এ একই algorithm বাস্তব query-র সঙ্গে ব্যবহার করুন। [তালিকায় ফিরুন](../README.md)।