Sorting ও Searching — কোন কাজ আগে কেন¶
Sorting তথ্যকে একটি নিয়মে সাজায়; searching সেই তথ্যের মধ্যে প্রয়োজনীয় অংশ খোঁজে। একবার ব্যবহার হলে সরল scan যথেষ্ট হতে পারে। একই data-তে অনেক query হলে sorting-এর এককালীন খরচ পরে বাঁচতে পারে।
আগে যা পড়বেন¶
- Array এবং index: position আর value আলাদা।
- দুটি sorted অংশ এক করা: কোন pointer এগোবে তা তুলনা ঠিক করে।
- Lower bound-এর ধারণা: উত্তর খোঁজার interval কীভাবে ছোট হয়।
একই input-এ তিনটি দৃষ্টিভঙ্গি¶
[4, 1, 4, 2] সাজিয়ে [1, 2, 4, 4] করতে হবে।
| পদ্ধতি | প্রতি ধাপে কী নিশ্চিত হয় | সময় | এই reference-এ অতিরিক্ত জায়গা |
|---|---|---|---|
| Bubble | একটি pass শেষে ডানের সবচেয়ে বড় মান স্থির | worst O(n²); আগে থেকেই sorted হলে O(n) | input copy-এর জন্য O(n) |
| Merge | ছোট sorted block জুড়ে বড় sorted block তৈরি | O(n log n) | O(n) |
| Three-way quicksort | ছোট / সমান / বড় partition আলাদা | সাধারণত O(n log n), worst O(n²) | O(n) |
Quicksort-এর সব implementation stable নয়। এখানে শেখানোর জন্য আলাদা partition list রাখা হয়েছে, তাই সমান key-র আগের ক্রম অক্ষত থাকে। In-place quicksort-এর space/stability-র দাবি এই implementation-এ প্রয়োগ করবেন না।
flowchart LR
A[অগোছালো data] --> B[তুলনা করে সাজান]
B --> C[Sorted keys]
C --> D[Lower bound]
C --> E[Upper bound]
D --> F[সমান key-র পরিসর]
E --> FSearch-এ interval কেন জরুরি¶
low অন্তর্ভুক্ত, high বাদ: শুরু [0, n)। Lower bound-এ values[mid] < target হলে low = mid + 1; অন্যথায় high = mid। শেষে দুই সীমা একই index। Target না থাকলেও এটি তার ঢোকার জায়গা। Upper bound-এ শুধু তুলনা বদলায়: <= target।
Input sorted না হলে এই discard-এর যুক্তি থাকে না। এমন ক্ষেত্রে আগে sort করুন অথবা linear scan ব্যবহার করুন।