এখানে আমরা কিছু সাজানোর পদ্ধতি দেখব। 200+ বাছাই কৌশল আছে। আমরা তাদের কয়েকটি দেখতে পাব। কিছু বাছাই কৌশল তুলনা ভিত্তিক বাছাই, কিছু অ-তুলনা ভিত্তিক বাছাই কৌশল।
তুলনা ভিত্তিক বাছাই কৌশলগুলি হল বুদ্বুদ সাজানো, নির্বাচন সাজানো, সন্নিবেশ সাজানো, মার্জ সাজানো, কুইকসর্ট, হিপ সর্ট ইত্যাদি। এই কৌশলগুলি তুলনা ভিত্তিক বাছাই হিসাবে বিবেচিত হয় কারণ এই কৌশলগুলিতে মানগুলি তুলনা করা হয়, এবং পৃথক পর্যায়গুলিতে সাজানো অবস্থানে স্থাপন করা হয়। এখানে আমরা এই কৌশলগুলির সময় জটিলতা দেখতে পাব।
| বিশ্লেষণ প্রকার | বুদবুদ সাজান | নির্বাচন বাছাই | সন্নিবেশ বাছাই | সর্ট মার্জ করুন | দ্রুত সাজান | হিপ সর্ট |
|---|---|---|---|---|---|---|
| সেরা কেস | O(n 2 ) | O(n 2 ) | O(n) | O(log n) | O(log n) | O(logn) |
| গড় কেস | O(n 2 ) | O(n 2 ) | O(n 2 ) | O(log n) | O(log n) | O(log n) |
| সবচেয়ে খারাপ ঘটনা | O(n 2) | O(n 2 ) | O(n 2 ) | O(log n) | O(n 2 ) | O(log n) |
কিছু বাছাই অ্যালগরিদম অ-তুলনা ভিত্তিক অ্যালগরিদম। এর মধ্যে কয়েকটি হল রেডিক্স সর্ট, বাকেট সর্ট, কাউন্ট সর্ট। এগুলি অ-তুলনা ভিত্তিক সাজানো কারণ এখানে বাছাই করার সময় দুটি উপাদান তুলনা করা হয় না। কৌশল কিছুটা ভিন্ন। এখন আমরা বিভিন্ন ধরণের বিশ্লেষণের উপর ভিত্তি করে তাদের মধ্যে পার্থক্য দেখতে পাব।
| বিশ্লেষণ প্রকার | Radix Sort (k হল সর্বাধিক সংখ্যা) | গণনা বাছাই (k হল গণনা অ্যারের আকার) | বালতি বাছাই (k হল বালতির সংখ্যা) |
|---|---|---|---|
| সেরা কেস | O(nk) | O(n + k) | O(n + k) |
| গড় কেস | O(nk) | O(n + k) | O(n + k) |
| সবচেয়ে খারাপ কেস | O(nk) | O(n + k) | O(n 2 ) |
বাছাই কৌশলগুলিকেও কিছু অন্যান্য পরামিতি ব্যবহার করে তুলনা করা যেতে পারে। কিছু বাছাই অ্যালগরিদম হল ইন-প্লেস বাছাই অ্যালগরিদম, এবং কিছু হল আউট-প্লেস বাছাই অ্যালগরিদম৷ যে অ্যালগরিদমগুলির জন্য কোনও অতিরিক্ত স্থানের প্রয়োজন হয় না তাকে ইন-প্লেস সর্টিং অ্যালগরিদম বলা হয়। যেমন Quicksort, heapsort অ্যালগরিদম ইন-প্লেস। কিন্তু মার্জ সর্ট হল আউট-প্লেস বাছাই কৌশল।
কিছু অ্যালগরিদম অনলাইন এবং কিছু অফলাইন। সাজানোর প্রক্রিয়া চলাকালীন অ্যালগরিদম যদি নতুন উপাদান গ্রহণ করে, তাকে অনলাইন বাছাই অ্যালগরিদম বলা হয়। উপরে উল্লিখিত কৌশলগুলি থেকে, সন্নিবেশ বাছাই হল অনলাইন সাজানোর কৌশল।
