একটা list-কে ক্রমে সাজানোর চারটা classic পদ্ধতি, পাশাপাশি।
মূল ধারণা
তাসের হাত সাজানোর উদাহরণ থেকে মূল ধারণাগুলো বোঝা যায়:
Bubble sort: পাশাপাশি দুটো element বারবার compare করুন, ক্রম ভুল হলে swap করুন। প্রতি pass-এ সবচেয়ে বড় তাসটা “bubble” হয়ে শেষে পৌঁছে যায়। সহজ, কিন্তু ধীর।
Insertion sort: এক এক করে তাস তুলে নিন, আর যে তাসগুলো আগে থেকে হাতে আছে তাদের মধ্যে ঠিক জায়গায় ঢুকিয়ে দিন।
Merge sort: তাসের গাদা দু-ভাগে ভাগ করুন, প্রতিটা ভাগ একইভাবে sort করুন, তারপর দুটো sorted গাদা merge করুন: সবসময় উপরের ছোট তাসটা আগে নিন। এটা divide and conquer।
Quick sort: একটা pivot তাস বেছে নিন; ছোট তাসগুলো তার বাঁয়ে আর বড়গুলো ডানে রাখুন। এখন pivot তার final জায়গায়; দুই পাশে একই কাজ repeat করুন।
Run করে দেখুন
নিজে চেষ্টা করুন
প্রতিটা algorithm একই সংখ্যার উপর run করুন আর box-গুলোর নিচে দেখানো comparisons-এর সংখ্যা মিলিয়ে দেখুন।
Bubble আর insertion-কে আগে থেকেই sorted list দিন। কোনটায় swap/shift কম লাগে?
উল্টো ক্রমে sorted list দিন (9, 8, 7, 6, 5, 4)। কোনটার সবচেয়ে বেশি কষ্ট হয়?
Quick sort: sorted list দিন। সেখানে শেষ item-কে pivot ধরা খারাপ সিদ্ধান্ত। ধাপের সংখ্যার কী হয়?
3, 3, 3, 1-এর মতো duplicate value দিন আর দেখুন প্রতিটা algorithm সমান item-গুলোকে কীভাবে সামলায়।
সাধারণ ভুল
Bubble sort-এর inner loop-এ off-by-one:a[j] আর a[j+1] compare করা হয়, তাই j-কে unsorted অংশের শেষের এক ঘর আগে থামতে হবে।
Merge sort: বাকি element ভুলে যাওয়া, এক পাশ শেষ হয়ে গেলে।
খারাপ pivot দিয়ে quick sort (সবসময় সবচেয়ে ছোট বা বড়) ধীর হয়ে O(n²) হয়ে যায়। আসল implementation-এ random বা median pivot নেওয়া হয়।
আসল Go code-এ নিজে sort লেখা:slices.Sort বা sort.Slice ব্যবহার করুন; এগুলো দ্রুত আর ভালোভাবে test করা।
Complexity
Bubble & insertion: O(n²) time complexity (প্রায় sorted data-তে insertion O(n)), O(1) space complexity। Merge sort: সবসময় O(n log n), বাড়তি O(n) space। Quick sort: গড়ে O(n log n), worst case O(n²), stack space O(log n)।