مرتب‌سازی سریع
QuicksortQuicksort یک pivot انتخاب می‌کند، عناصر را نسبت به pivot partition می‌کند و سپس بخش‌های ایجادشده را بازگشتی مرتب می‌کند.
اول این مفهوم را در ذهن نگه دار
Quicksort یک pivot انتخاب می‌کند، عناصر را نسبت به pivot partition می‌کند و سپس بخش‌های ایجادشده را بازگشتی مرتب می‌کند.
چطور کار می‌کند؟ ساده و مرحله‌ای
زمان متوسط O(n log n) است، اما pivotهای بد می‌توانند بدترین حالت O(n²) بسازند.
نسخه in-place حافظه Array اضافی کمی می‌خواهد ولی recursion همچنان stack مصرف می‌کند.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
ببین هر pass/partition/merge چه بخشی را قطعی می‌کند.
ناحیه‌ای را که دیگر نهایی شده دنبال کن.
تعداد comparison، swap/move و حافظه اضافه را تحلیل کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای مرتب‌سازی سریع هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function quickSort(a) {
if (a.length <= 1) return a;
const pivot = a[Math.floor(a.length / 2)];
const left = a.filter(x => x < pivot);
const equal = a.filter(x => x === pivot);
const right = a.filter(x => x > pivot);
return [...quickSort(left), ...equal, ...quickSort(right)];
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
avg O(n log n), worst O(n²)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- انتخاب را بر اساس اندازه داده، میزان مرتب بودن، بازه key، stable بودن و محدودیت حافظه انجام بده.
کجا معمولاً اشتباه می‌کنیم؟
- فقط Average Big-O را مقایسه نکن.
- stability، in-place بودن، عمق recursion و فرض‌های مربوط به domain را فراموش نکن.
مدل یک پاسخ حرفه‌ای
در جواب حرفه‌ای درباره pivot و partition scheme حرف بزن. گفتن صرف O(n log n) کافی نیست چون بدترین حالت O(n²) نکته مهم Quicksort است.
مرتب‌سازی سریع چه مسئله‌ای را حل می‌کند؟
Quicksort یک pivot انتخاب می‌کند، عناصر را نسبت به pivot partition می‌کند و سپس بخش‌های ایجادشده را بازگشتی مرتب می‌کند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا avg O(n log n), worst O(n²) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
فقط Average Big-O را مقایسه نکن.