مرتب‌سازی سطلی
Bucket Sortمرتب‌سازی سطلی یک الگوریتم از دسته مرتب‌سازی است. این الگوریتم مرتب‌سازی داده‌ها را با یک استراتژی مشخص مقایسه یا توزیع، به ترتیب موردنظر می‌چیند.
اول این مفهوم را در ذهن نگه دار
مرتب‌سازی سطلی یک الگوریتم از دسته مرتب‌سازی است. این الگوریتم مرتب‌سازی داده‌ها را با یک استراتژی مشخص مقایسه یا توزیع، به ترتیب موردنظر می‌چیند.
چطور کار می‌کند؟ ساده و مرحله‌ای
برای فهم مرتب‌سازی سطلی ابتدا invariant و stateای را پیدا کن که در هر مرحله تغییر می‌کند.
پیچیدگی معمول این موضوع avg O(n+k) است؛ آن را از روی loop، recursion، عملیات ساختمان داده و constraintهای ورودی تحلیل کن، نه فقط از حفظ.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
ببین هر pass/partition/merge چه بخشی را قطعی می‌کند.
ناحیه‌ای را که دیگر نهایی شده دنبال کن.
تعداد comparison، swap/move و حافظه اضافه را تحلیل کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای مرتب‌سازی سطلی هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
avg O(n+k)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- انتخاب را بر اساس اندازه داده، میزان مرتب بودن، بازه key، stable بودن و محدودیت حافظه انجام بده.
کجا معمولاً اشتباه می‌کنیم؟
- فقط Average Big-O را مقایسه نکن.
- stability، in-place بودن، عمق recursion و فرض‌های مربوط به domain را فراموش نکن.
مدل یک پاسخ حرفه‌ای
برای توضیح حرفه‌ای مرتب‌سازی سطلی در مصاحبه، مسئله‌ای که حل می‌کند، invariant، state یا ساختمان داده اصلی، پیچیدگی avg O(n+k) و شرایطی که باعث می‌شود روش دیگری انتخاب کنی را بگو.
مرتب‌سازی سطلی چه مسئله‌ای را حل می‌کند؟
مرتب‌سازی سطلی یک الگوریتم از دسته مرتب‌سازی است. این الگوریتم مرتب‌سازی داده‌ها را با یک استراتژی مشخص مقایسه یا توزیع، به ترتیب موردنظر می‌چیند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا avg O(n+k) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
فقط Average Big-O را مقایسه نکن.