مرتب‌سازی حبابی (Bubble Sort)
مرتب‌سازی حبابی: ساده‌ترین الگوریتم مرتب‌سازی، مقایسه و جابه‌جایی جفتی، بهینه‌سازی با پرچم swapped
مرتب‌سازی حبابی چیست؟
Bubble Sort ساده‌ترین الگوریتم مرتب‌سازی: هر دو عنصر مجاور را مقایسه و در صورت نیاز جابه‌جا می‌کنیم. با هر پاس، بزرگ‌ترین عنصر باقی‌مانده مثل حباب به انتهای لیست «شناور» می‌شود!
الگوریتم
- از ابتدا، هر جفت مجاور را مقایسه کن
- اگر ترتیب غلط بود، جابه‌جا کن
- بعد از پاس اول، بزرگ‌ترین در آخر است
- تکرار تا n−1 پاس (هر بار یک عنصر کمتر)
مثال گام‌به‌گام
[5, 2, 8, 1]
پاس ۱:
(5,2) جابه‌جا -> [2, 5, 8, 1]
(5,8) اوکی -> [2, 5, 8, 1]
(8,1) جابه‌جا -> [2, 5, 1, 8] ← ۸ در جای نهایی
پاس ۲:
(2,5) اوکی -> [2, 5, 1, 8]
(5,1) جابه‌جا -> [2, 1, 5, 8] ← ۵ در جای نهایی
پاس ۳:
(2,1) جابه‌جا -> [1, 2, 5, 8] ✓ مرتب شد!پیچیدگی
| حالت | پیچیدگی |
|---|---|
| بدترین (معکوس) | O(n²) |
| میانگین | O(n²) |
| بهترین (مرتب + بهینه‌سازی) | O(n) |
| حافظه | O(1) — درجا |
بهینه‌سازی: پرچم swapped
اگر در یک پاس کامل هیچ جابه‌جایی انجام نشد، یعنی لیست مرتب است — بلافاصله تمام کنید! این بهینه‌سازی بهترین حالت را O(n) می‌کند.
مزایا و معایب
- ✓ بسیار ساده برای فهمیدن و یادگیری
- ✓ پایدار (Stable): ترتیب عناصر برابر حفظ می‌شود
- ✗ بسیار کند برای داده بزرگ: O(n²)
- ✗ در عمل هرگز استفاده نمی‌شود!
نکته: چرا یادش می‌کنیم؟ چون ساده‌ترین مقدمه‌ست بر مفهوم «الگوریتم مرتب‌سازی» و تحلیل پیچیدگی. در مصاحبه هم به‌عنوان نقطه شروع مقایسه با الگوریتم‌های بهتر مطرح می‌شود.
جمع‌بندی
- مقایسه جفتی مجاور + جابه‌جایی؛ حباب‌شدن بزرگ‌ترین به انتها
- O(n²) — فقط آموزشی
- بهینه‌سازی swapped بهترین حالت را O(n) می‌کند
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.