مرتب کردن یک لیست با مقایسه‌های ساده
مرتب‌سازی حبابی یکی از ساده‌ترین الگوریتم‌های مرتب‌سازی است. ایده‌ی آن این است که به‌طور مکرر عناصر مجاور را با هم مقایسه کنیم و در صورت اشتباه بودن ترتیب آن‌ها (بزرگ‌تر قبل از کوچک‌تر)، جای آن‌ها را عوض کنیم. این کار را آن‌قدر تکرار می‌کنیم تا کل لیست مرتب شود.
نام این الگوریتم از این‌جا می‌آید که در هر مرحله، بزرگ‌ترین عدد باقی‌مانده کم‌کم مانند حباب به انتهای لیست «بالا می‌آید».
- شروع
- دریافت لیست اعداد
- برای هر دور از ابتدا تا انتهای لیست: هر دو عنصر مجاور را مقایسه کن
- اگر عنصر چپ بزرگ‌تر از عنصر راست بود، جای آن‌ها را عوض کن
- این کار را برای همه‌ی دورها تکرار کن تا هیچ جابه‌جایی لازم نباشد
- نمایش لیست مرتب‌شده
- پایان
def bubble_sort(numbers):
n = len(numbers)
for i in range(n - 1):
for j in range(n - 1 - i):
if numbers[j] > numbers[j + 1]:
numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
return numbers
data = [64, 25, 12, 22, 11]
print(bubble_sort(data)) # [11, 12, 22, 25, 64]در حلقه‌ی بیرونی، هر بار مطمئن می‌شویم که حداقل یک عنصر بزرگ به جای درست خود در انتها منتقل شده، به همین دلیل در حلقه‌ی داخلی، محدوده‌ی بررسی هر بار کوچک‌تر می‌شود (n - 1 - i). مرتب‌سازی حبابی برای یادگیری مفهوم مرتب‌سازی عالی است، اما برای لیست‌های بزرگ کارآمد نیست؛ در فصل بعد دلیل ریاضی این موضوع را با مفهوم پیچیدگی زمانی بررسی می‌کنیم.