مرتب‌سازی حبابی
جفت‌های کنار هم را مقایسه و در صورت نیاز جابه‌جا می‌کند؛ در هر گذر، بزرگ‌ترین عضو مثل حباب به انتها می‌رود.
در هر گذر، جفت‌های کنار هم از چپ به راست مقایسه می‌شوند و اگر ترتیبشان غلط بود جابه‌جا می‌شوند. بزرگ‌ترین عضو بخش نامرتب مثل حباب تا انتهای آن بالا می‌آید و در جای نهایی‌اش می‌نشیند. پس هر گذر یک خانه کوتاه‌تر از قبلی است.
ادامه‌ی توضیح ↓- زمان:
O(n²), O(n) if already sorted - حافظه:
O(1) - CLRS، فصل ۲
- جانسون‌باو، فصل ۴
شش عدد درهم؛ چند گذر لازم است تا همه‌ی حباب‌ها بالا بیایند.
def bubble_sort(a):n = len(a)for end in range(n - 1, 0, -1):swapped = Falsefor i in range(end):if a[i] > a[i + 1]:a[i], a[i + 1] = a[i + 1], a[i]swapped = Trueif not swapped:breakreturn a
شروع اجرا
متغیرهای محلی
نارنجی = در همین گام عوض شد
a list
Call stack
- bubble_sort()خط 1
رشد تعداد عملیات با اندازه‌ی ورودی
میانگین ۱۲ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.
- comparisons
- swaps
- ورودی فعلی (n=6)
نمایش به شکل جدول
| n | comparisons | swaps |
|---|---|---|
| 4 | 5.7 | 3.3 |
| 6 | 13.6 | 7.6 |
| 8 | 24.8 | 12 |
| 10 | 42.6 | 21.3 |
| 12 | 61.3 | 29.4 |
| 14 | 84.9 | 43 |
| 16 | 112 | 58.4 |
توضیح
ایده
در هر گذر، جفت‌های کنار هم از چپ به راست مقایسه می‌شوند و اگر ترتیبشان غلط بود جابه‌جا می‌شوند. بزرگ‌ترین عضو بخش نامرتب مثل حباب تا انتهای آن بالا می‌آید و در جای نهایی‌اش می‌نشیند. پس هر گذر یک خانه کوتاه‌تر از قبلی است.
توقف زودهنگام
اگر گذری هیچ جابه‌جایی نداشت، آرایه مرتب است و ادامه دادن بی‌فایده است. با همین ترفند، روی ورودی مرتب فقط یک گذر (n − 1 مقایسه) لازم است.
هزینه
- بدترین و حالت متوسط
O(n²)، بهترین حالتO(n). - حافظه‌ی اضافه
O(1)؛ مرتب‌سازی پایدار است چون فقط عضوهای کنار هم و فقط وقتی>هستند جابه‌جا می‌شوند.
«خرگوش و لاک‌پشت»
عضو بزرگ در ابتدای آرایه (خرگوش) در یک گذر تا انتها می‌دود، ولی عضو کوچک در انتها (لاک‌پشت) در هر گذر فقط یک خانه جلو می‌آید. ورودی «لاک‌پشت» این را نشان می‌دهد.
در trace به چه چیزی نگاه کنی
- فلش
endمرز بخش نامرتب است؛ میله‌های بعد از آن در جای نهایی‌اند. - شمار
swapرا با تعداد جفت‌های نابه‌جا (وارونگی‌ها) مقایسه کن: دقیقاً برابرند.