مرتبسازی حبابی در پایتون (Bubble Sort) با مثال و کد
این قطعه کد پایتون توسط یکی از کاربران در کامپایلر آنلاین پایتون نوشته و اجرا شده است. شما هم میتوانید کدهای خود را به صورت آنلاین تست کنید.
زبان: پایتون
مرتبسازی حبابی چگونه کار میکند؟
مرتبسازی حبابی (Bubble Sort) یکی از سادهترین الگوریتمهای مرتبسازی است. در این روش، عناصر لیست را دوبهدو مقایسه میکنیم و اگر ترتیب آنها درست نباشد، جایشان را عوض میکنیم. این فرایند مانند حبابهایی است که به سطح آب میآیند؛ بزرگترین عنصر در هر دور به انتهای لیست منتقل میشود.
ورودی: یک لیست از اعداد (یا هر داده قابل مقایسه).
خروجی: همان لیست به صورت مرتبشده (صعودی).
مراحل اجرا:
- از ابتدای لیست شروع میکنیم.
- هر جفت عنصر مجاور را مقایسه میکنیم.
- اگر عنصر چپ بزرگتر از عنصر راست باشد، آنها را جابجا میکنیم.
- بعد از هر دور، بزرگترین عنصر در جای خود قرار میگیرد.
- این کار را تا زمانی که نیازی به جابجایی نباشد ادامه میدهیم.
برای مثال، در لیست [5, 1, 4, 2, 8] پس از دور اول، عدد 8 به انتهای لیست منتقل میشود.
پیچیدگی زمانی:
- بدترین حالت: O(n²)
- حالت متوسط: O(n²)
- بهترین حالت (با بهینهسازی): O(n) زمانی که لیست از قبل مرتب باشد.
پیچیدگی فضایی: O(1) زیرا مرتبسازی درجا انجام میشود.
این الگوریتم برای آموزش مفاهیم پایه مرتبسازی عالی است، اما برای دادههای بزرگ کارایی ندارد. کد بالا را میتوانید مستقیماً اجرا کنید و نتیجه را ببینید.