مرتب سازی حبابی (Bubble Sort)
«مرتب سازی حبابی (Bubble Sort)» آرایه را از کم به زیاد می چیند. هر بار دو همسایه را مقایسه می کند. سپس جا به جا می کند تا بزرگ ترها آرام آرام به آخر «حباب» بزنند.
ایده ساده مرتب سازی حبابی
از ابتدا تا انتها برو. هر جفت همسایه را مقایسه کن. اگر ترتیب بد بود، جابه جا کن. این کار چند دور تکرار می شود تا آرایه مرتب شود.
پیاده سازی پایه در پایتون
کد زیر نسخه پایه است. در هر دور، بزرگ ترین مقدار به آخر می رود.
mylist = [64, 34, 25, 12, 22, 11, 90, 5]
n = len(mylist)
for i in range(n - 1):
for j in range(n - i - 1):
if mylist[j] > mylist[j + 1]:
mylist[j], mylist[j + 1] = mylist[j + 1], mylist[j]
print(mylist)
بهبود با پرچم جابه جایی
اگر در یک دور هیچ جابه جایی نشد، آرایه قبلاً مرتب است. بنابراین می توانیم زودتر متوقف شویم.
mylist = [7, 3, 9, 12, 11]
n = len(mylist)
for i in range(n - 1):
swapped = False
for j in range(n - i - 1):
if mylist[j] > mylist[j + 1]:
mylist[j], mylist[j + 1] = mylist[j + 1], mylist[j]
swapped = True
if not swapped:
break
print(mylist)
گام های عملی
- لیست نامرتب را آماده کن.
- از ابتدای لیست حرکت کن.
- دو همسایه را مقایسه کن.
- اگر ترتیب بد بود، جابه جا کن.
- دورها را تکرار کن تا مرتب شود.
پیچیدگی زمانی مرتب سازی حبابی
تعداد مقایسه ها تقریباً n×n است. بنابراین «پیچیدگی زمانی (Time Complexity)» برابر O(n^2) است. برای لیست های بزرگ کند می شود.
نکته: برای جست وجو روی داده مرتب، جستجوی دودویی سریع تر عمل می کند.
پیوندها
راهنمای کامل مرتب سازی حبابی در همین صفحه است. برای الگوریتم بعدی به مرتب سازی انتخابی سر بزن.
منبع: W3Schools Bubble Sort با شبیه سازی تصویری.
جمع بندی سریع
- ساده اما کند روی لیست بزرگ.
- در هر دور، بزرگ ترین به آخر می رود.
- بهبود «swapped» توقفِ زودهنگام می دهد.
- پیچیدگی زمانی O(n^2) است.
- برای داده بزرگ، سراغ روش های سریع تر برو.