الگوریتم‌های مرتب‌سازی از مفاهیم مهم در علوم کامپیوتر و برنامه‌نویسی هستند. این الگوریتم‌ها برای ترتیب داده‌ها به ترتیبی مشخص بر اساس مقایسه مقادیر استفاده می‌شوند. یکی از ساده‌ترین الگوریتم‌های مرتب‌سازی، الگوریتم مرتب‌سازی حبابی است. در این مقاله، به بررسی الگوریتم مرتب‌سازی حبابی، کارکرد آن، پیچیدگی زمانی و نحوه پیاده‌سازی آن می‌پردازیم.
الگوریتم مرتب‌سازی حبابی یکی از ساده‌ترین الگوریتم‌های مرتب‌سازی است و برای مرتب‌سازی آرایه‌ها و لیست‌ها به کار می‌رود. عملکرد این الگوریتم بسیار ساده است؛ آن را می‌توان به صورت زیر توصیف کرد:
- شروع از ابتدای آرایه و مقایسه دو به دو اعضای متوالی.
- اگر عنصر بعدی از عنصر فعلی کوچکتر باشد، آن‌ها را جابجا کنید.
- این کار را برای تمامی اعضا تا آخر آرایه انجام دهید.
- با اتمام یک مرور کامل از آرایه، عنصر بزرگترین مقدار به انتهای آرایه منتقل می‌شود.
- تکرار این مراحل برای اعضای باقی‌مانده آرایه تا زمانی که آرایه کاملاً مرتب شود.
پیچیدگی زمانی این الگوریتم در بدترین حالت O(n^2) است. این به این معناست که در بدترین حالت، تعداد مقایسات و جابجایی‌ها برابر با n*(n-1)/2 خواهد بود که n تعداد عناصر آرایه است. این الگوریتم برای آرایه‌های کوچک به خوبی عمل می‌کند، اما برای آرایه‌های بزرگ، کارایی آن پایین می‌آید.
نمونه کد پیاده‌سازی الگوریتم مرتب‌سازی حبابی در زبان Python به شکل زیر است:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
# نمونه استفاده
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("آرایه مرتب شده:", arr)الگوریتم مرتب‌سازی حبابی البته به عنوان یکی از الگوریتم‌های آموزشی و تمرینی مورد استفاده قرار می‌گیرد و در برنامه‌های واقعی نادراً استفاده می‌شود. الگوریتم‌های مرتب‌سازی موثر‌تری مانند مرتب‌سازی ادغامی (Merge Sort) و مرتب‌سازی سریع (Quick Sort) برای مرتب‌سازی داده‌ها استفاده می‌شوند.
دیدگاه‌ها