কনটেন্টে যান

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

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

প্রশ্ন ও উদাহরণ

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

  • Input: [4, 1, 4, 2]
  • Output: [1, 2, 4, 4]

ভিত্তির ধারণা

আগে পড়ুন: sorting/searching-এর ধারণা, array ও index। এরপর partition / explicit stack-এর কাজটি নিজের ভাষায় বলুন।

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

ধাপে ধাপে সমাধান

ধাপ ছোট সমান বড়
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 হওয়ার নিশ্চয়তা নেই।

কোড ও ব্যাখ্যা

সম্পূর্ণ implementation আছে 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-এর সঙ্গে মিলিয়ে দেখুন।

খরচ ও সাধারণ ভুল

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

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

শেখা ও পরের অনুশীলন

পরীক্ষাগুলো দিয়ে output, stability ও edge case মিলিয়ে নিন:

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

তারপর পণ্যের catalogue guided challenge-এ একই algorithm বাস্তব query-র সঙ্গে ব্যবহার করুন। তালিকায় ফিরুন।