مرتب‌سازی حبابی
Bubble SortBubble Sort جفت‌های مجاور را مقایسه می‌کند و اگر ترتیب اشتباه باشد swap می‌کند؛ در هر دور مقدارهای بزرگ‌تر به سمت انتهای Array حرکت می‌کنند.
اول این مفهوم را در ذهن نگه دار
Bubble Sort جفت‌های مجاور را مقایسه می‌کند و اگر ترتیب اشتباه باشد swap می‌کند؛ در هر دور مقدارهای بزرگ‌تر به سمت انتهای Array حرکت می‌کنند.
چطور کار می‌کند؟ ساده و مرحله‌ای
بعد از یک pass کامل، بزرگ‌ترین مقدار بخش نامرتب در جای نهایی خودش قرار می‌گیرد.
با flag مربوط به swap می‌توان برای Array از قبل مرتب‌شده بهترین حالت O(n) داشت.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
ببین هر pass/partition/merge چه بخشی را قطعی می‌کند.
ناحیه‌ای را که دیگر نهایی شده دنبال کن.
تعداد comparison، swap/move و حافظه اضافه را تحلیل کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای مرتب‌سازی حبابی هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function bubbleSort(input) {
const a = [...input];
for (let end = a.length - 1; end > 0; end--) {
let swapped = false;
for (let i = 0; i < end; i++) {
if (a[i] > a[i + 1]) {
[a[i], a[i + 1]] = [a[i + 1], a[i]];
swapped = true;
}
}
if (!swapped) break;
}
return a;
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
O(n²)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- انتخاب را بر اساس اندازه داده، میزان مرتب بودن، بازه key، stable بودن و محدودیت حافظه انجام بده.
کجا معمولاً اشتباه می‌کنیم؟
- محدوده انتهایی که هر دور کوچک‌تر می‌شود را فراموش نکن.
- برای workload بزرگ معمولاً O(n²) انتخاب مناسبی نیست.
مدل یک پاسخ حرفه‌ای
بیشتر برای نشان دادن مفهوم sorting، stability و تحلیل best/average/worst case مناسب است، نه انتخاب پیش‌فرض production.
مرتب‌سازی حبابی چه مسئله‌ای را حل می‌کند؟
Bubble Sort جفت‌های مجاور را مقایسه می‌کند و اگر ترتیب اشتباه باشد swap می‌کند؛ در هر دور مقدارهای بزرگ‌تر به سمت انتهای Array حرکت می‌کنند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(n²) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
محدوده انتهایی که هر دور کوچک‌تر می‌شود را فراموش نکن.