এখানে আমরা কিছু সর্টিং মেথড দেখব। ২০০+ সর্টিং টেকনিক রয়েছে। আমরা 그중 কিছু দেখব। কিছু সর্টিং টেকনিক কমপ্যারিজন-বেসড সর্ট, কিছু নন-কমপ্যারিজন-বেসড সর্টিং টেকনিক।
কমপ্যারিজন বেসড সর্টিং টেকনিক হচ্ছে বাবল সর্ট, সিলেকশন সর্ট, ইনসারশন সর্ট, মার্জ সর্ট, কুইকসর্ট, হিপ সর্ট ইত্যাদি। এই টেকনিকগুলো কমপ্যারিজন বেসড কারণ এখানে মানগুলো তুলনা করা হয় এবং ভিন্ন ফেজে সোর্টেড পজিশনে রাখা হয়। এখানে আমরা এই টেকনিকগুলোর টাইম কমপ্লেক্সিটি দেখব।
| Analysis Type | Bubble Sort | Selection Sort | Insertion Sort | Merge Sort | Quick Sort | Heap Sort |
|---|---|---|---|---|---|---|
| Best Case | O(n²) | O(n²) | O(n) | O(n log n) | O(n log n) | O(n log n) |
| Average Case | O(n²) | O(n²) | O(n²) | O(n log n) | O(n log n) | O(n log n) |
| Worst Case | O(n²) | O(n²) | O(n²) | O(n log n) | O(n²) | O(n log n) |
কিছু সর্টিং অ্যালগরিদম নন-কমপ্যারিজন বেসড। उनमें রেডিক্স সর্ট, বাকেট সর্ট, কাউন্ট সর্ট অন্য কিছু। এগুলো নন-কমপ্যারিজন বেসড কারণ সর্ট করার সময় দুটি এলিমেন্ট তুলনা করা হয় না। টেকনিকগুলো কিছুটা ভিন্ন। এখন আমরা বিভিন্ন টাইপের অ্যানালিসিসের ভিত্তিতে তাদের পার্থক্য দেখব।
| Analysis Type | Radix Sort (k is maximum digit) | Counting Sort (k is size of count array) | Bucket Sort (k is number of buckets) |
|---|---|---|---|
| Best Case | O(nk) | O(n + k) | O(n + k) |
| Average Case | O(nk) | O(n + k) | O(n + k) |
| Worst Case | O(nk) | O(n + k) | O(n²) |
সর্টিং টেকনিক অন্য কিছু প্যারামিটার দিয়েও তুলনা করা যায়। কিছু সর্টিং অ্যালগরিদম ইন-প্লেস সর্টিং অ্যালগরিদম, আর কিছু আউট-প্লেস সর্টিং অ্যালগরিদম। যেসব অ্যালগরিদম কোনো এক্সট্রা স্পেস দরকার করে না সেগুলো ইন-প্লেস সর্টিং অ্যালগরিদম। যেমন কুইকসর্ট, হিপসর্ট ইন-প্লেস। কিন্তু মার্জ সর্ট আউট-প্লেস সর্টিং টেকনিক।
কিছু অ্যালগরিদম অনলাইন আর কিছু অফলাইন। যদি অ্যালগরিদম সর্টিং প্রসেস চলাকালীন নতুন এলিমেন্ট গ্রহণ করে, সেটাকে অনলাইন সর্টিং অ্যালগরিদম বলা হয়। উপরে বর্ণিত টেকনিকগুলোতে, ইনসারশন সর্ট অনলাইন সর্টিং টেকনিক।
