مرتب‌سازی شمارشی
Counting SortCounting Sort به‌جای مقایسه عناصر، تعداد تکرار هر key را می‌شمارد و بعد خروجی را بر اساس همین شمارش‌ها می‌سازد.
اول این مفهوم را در ذهن نگه دار
Counting Sort به‌جای مقایسه عناصر، تعداد تکرار هر key را می‌شمارد و بعد خروجی را بر اساس همین شمارش‌ها می‌سازد.
چطور کار می‌کند؟ ساده و مرحله‌ای
وقتی keyها عدد صحیح در یک بازه نسبتاً کوچک باشند بسیار سریع است.
پیچیدگی به n + k وابسته است؛ اگر بازه مقادیر خیلی بزرگ و sparse باشد حافظه هدر می‌رود.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
ببین هر pass/partition/merge چه بخشی را قطعی می‌کند.
ناحیه‌ای را که دیگر نهایی شده دنبال کن.
تعداد comparison، swap/move و حافظه اضافه را تحلیل کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای مرتب‌سازی شمارشی هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function countingSort(a, max = Math.max(...a)) {
const count = Array(max + 1).fill(0);
for (const x of a) count[x]++;
const out = [];
for (let value = 0; value < count.length; value++) {
for (let c = 0; c < count[value]; c++) out.push(value);
}
return out;
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
O(n + k)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- انتخاب را بر اساس اندازه داده، میزان مرتب بودن، بازه key، stable بودن و محدودیت حافظه انجام بده.
کجا معمولاً اشتباه می‌کنیم؟
- فقط Average Big-O را مقایسه نکن.
- stability، in-place بودن، عمق recursion و فرض‌های مربوط به domain را فراموش نکن.
مدل یک پاسخ حرفه‌ای
توضیح بده چرا می‌تواند از محدودیت comparison sortها عبور کند: از اطلاعات domain اعداد استفاده می‌کند و فقط مقایسه دوتایی انجام نمی‌دهد.
مرتب‌سازی شمارشی چه مسئله‌ای را حل می‌کند؟
Counting Sort به‌جای مقایسه عناصر، تعداد تکرار هر key را می‌شمارد و بعد خروجی را بر اساس همین شمارش‌ها می‌سازد.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(n + k) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
فقط Average Big-O را مقایسه نکن.