Sorting ও Searching অ্যালগরিদমের Time ও Space Complexity তুলনা

Sorting অ্যালগরিদমের তুলনামূলক তালিকা

সরকারি চাকরির পরীক্ষায় নিচের চার্ট থেকে প্রতি বছরই ১–২টি প্রশ্ন আসে:

Algorithm        Best         Average      Worst        Space     Stable?
-------------------------------------------------------------------------
Bubble Sort      O(n)         O(n²)        O(n²)        O(1)      Yes
Selection Sort   O(n²)        O(n²)        O(n²)        O(1)      No
Insertion Sort   O(n)         O(n²)        O(n²)        O(1)      Yes
Merge Sort       O(n log n)   O(n log n)   O(n log n)   O(n)      Yes
Quick Sort       O(n log n)   O(n log n)   O(n²)        O(log n)  No
Heap Sort        O(n log n)   O(n log n)   O(n log n)   O(1)      No
Counting Sort    O(n + k)     O(n + k)     O(n + k)     O(k)      Yes

• প্রায় সাজানো (Nearly Sorted) ডেটার জন্য সেরা: Insertion Sort, কারণ এটি O(n) সময়ে কাজ শেষ করে।
• সবচেয়ে কম সংখ্যক Swap করে: Selection Sort, সর্বোচ্চ O(n) সংখ্যক swap লাগে।
• Quick Sort-এর Worst Case: অ্যারে আগে থেকেই সাজানো থাকলে এবং প্রথম বা শেষ উপাদানকে pivot ধরলে সময় লাগে O(n²)। Randomized pivot বা median-of-three নিলে এটি এড়ানো যায়।
• Linked List সর্ট করার জন্য সেরা: Merge Sort, কারণ র‍্যান্ডম অ্যাক্সেস লাগে না এবং অতিরিক্ত অ্যারে ছাড়া O(1) পয়েন্টার পরিবর্তনে মার্জ করা যায়।
• Comparison-based সর্টিংয়ের নিচের সীমা (Lower Bound): যেকোনো তুলনাভিত্তিক সর্টিং অ্যালগরিদমে worst-case-এ অন্তত Ω(n log n) তুলনা প্রয়োজন।

• Linear Search: Unsorted ডেটায় O(n)।
• Binary Search: কেবল Sorted ডেটায় প্রযোজ্য; সময় O(log n), iterative-এ space O(1)।
• Binary Search-এ integer overflow এড়াতে মধ্যবিন্দু বের করার নিরাপদ সূত্র: mid = low + (high - low) / 2।