কনটেন্টে যান

Bubble sort — pass ধরে সাজানো

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

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

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

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

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

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

প্রতি pass-এ পাশাপাশি দুটি মান তুলনা করুন। বাঁয়ের মান বড় হলেই swap করুন। সবচেয়ে বড় অস্থির মানটি ডানে চলে যাবে।

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

শুরু তুলনার পর অবস্থা
[4,1,3,2] 4 ও 1 বদলে [1,4,3,2]
[1,4,3,2] 4 ও 3 বদলে [1,3,4,2]
[1,3,4,2] 4 ও 2 বদলে [1,3,2,4]
দ্বিতীয় pass [1,2,3,4]; এবার শেষ দুই ঘর স্থির

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

ইঙ্গিত: কোনো pass-এ swap না হলে থামুন। সমান মানে swap না করলে আগের ক্রম থাকে।

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

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

Python
from practice.sorting_lab import bubble_sort

print(bubble_sort([4, 1, 3, 2]))

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

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

Worst O(n²); early-exit best O(n)। Reference input copy রাখায় 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-র সঙ্গে ব্যবহার করুন। তালিকায় ফিরুন।