مرتب‌سازی حبابی (bubble sort) در پایتون

مرتب‌سازی حبابی یک الگوریتم آسان در میان مرتب‌سازی‌های مختلف است. ما آن را به عنوان اولین الگوریتم مرتب‌سازی یاد می‌گیریم. یادگیری آن آسان و بسیار شهودی است. اجرای آن در کد نیز آسان و برای توسعه‌دهندگان نرم‌افزار مبتدی بسیار مفید و کاربردی است.

بیایید مفهوم مرتب‌سازی حبابی را درک کنیم.

مرتب‌سازی حبابی از منطق ساده‌ای استفاده می‌کند و با تکرار جابه‌جایی عناصر مجاور اگر در ترتیب صحیح نباشند آن ها را جابجا می کند. به این صورت که دو عنصر را با هم مقایسه و اگر عنصر اول از عنصر دوم بزرگتر باشد، آن دو را جابه‌جا می‌کند؛ در غیر اینصورت به جفت بعدی از عناصر برای مقایسه ادامه می‌دهد.

بیایید با یک مثال آن را درک کنیم :

ما یک لیست از عناصر ایجاد می‌کنیم که اعداد صحیح را ذخیره می‌کند

list1 = [5, 3, 8, 6, 7, 2]

در اینجا الگوریتم عناصر را مرتب می‌کند

[5, 3, 8, 6, 7, 2]  

این الگوریتم ابتدا دو عنصر اول را مقایسه می‌کند و در اینجا 5>3 است، بنابراین عناصر با یکدیگر جابجا می‌شوند. حالا ما لیست جدیدی داریم:

[3، 5، 8، 6، 7، 2]

در مقایسه دوم، 5 کمتر از 8 است، بنابراین جابجایی انجام می‌شود:

[3، 5، 8، 6، 7، 2]

در مقایسه سوم، 8 بزرگتر از 6 است، بنابراین جابجایی انجام می‌شود:

[3، 5، 6، 8، 7، 2]

در مقایسه چهارم، 8 بزرگتر از 7 است، بنابراین یک جابجایی دیگر انجام می‌شود:

[3، 5، 6، 7، 8، 2]

در مقایسه پنجم، 8 بزرگتر از 2 است، بنابراین جابجایی انجام می‌شود:

[3، 5، 6، 7، 2، 8]

در اینجا دور اول تکمیل شده و ما عنصر بزرگترین را در انتها داریم. حالا نیاز داریم به (len(list1) - 1)

[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 7, 2, 8]

در اینجا، 3 < 5 است، بنابراین هیچ جابه‌جایی انجام نمی‌شود.

[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 7, 2, 8] 

در اینجا، 5 < 6 است، بنابراین هیچ جابه‌جایی انجام نمی‌شود.

[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 7, 2, 8] 

در اینجا، 6 < 7 است، بنابراین هیچ جابه‌جایی انجام نمی‌شود.

[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 2, 7, 8] 

در اینجا، 7 > 2 است، بنابراین جابه‌جایی انجام می‌شود. حالا

[3, 5, 6, 2, 7, 8] - > [3, 5, 6, 2, 7, 8] 

در اینجا، 7 < 8 است، بنابراین هیچ جابه‌جایی انجام نمی‌شود.

[3, 5, 6, 2, 7, 8] -> [3, 5, 6, 7, 2, 8] 

در اینجا، 3 < 5 است، بنابراین هیچ جابه‌جایی انجام نمی‌شود.

[3, 5, 6, 2, 7, 8] -> [3, 5, 6, 7, 2, 8]

در اینجا، 5 < 6 است، بنابراین هیچ جابه‌جایی انجام نمی‌شود.

[3, 5, 6, 2, 7, 8] -> [3, 5, 2, 6, 7, 8]

در اینجا، 6 < 2 است، بنابراین جابه‌جایی انجام می‌شود.

[3, 5, 2, 6, 7, 8] -> [3, 5, 2, 6, 7, 8] 

در اینجا، 6 < 7 است، بنابراین هیچ جابه‌جایی انجام نمی‌شود. حالا

[3, 5, 2, 6, 7, 8] -> [3, 5, 2, 6, 7, 8] 

در اینجا، 7 < 8 است، بنابراین جابه‌جایی انجام می‌شود.

این تکرار ها تا زمان مرتب شدن لیست ادامه می یابد.

[3, 5, 2, 6, 7, 8] - > [3, 5, 2, 6, 7, 8]
[3, 5, 2, 6, 7, 8] - > [3, 2, 5, 6, 7, 8]
[3, 2, 5, 6, 7, 8] - > [3, 2, 5, 6, 7, 8]
[3, 2, 5, 6, 7, 8] - > [3, 2, 5, 6, 7, 8]
[3, 2, 5, 6, 7, 8] - > [3, 2, 5, 6, 7, 8]

[3, 2, 5, 6, 7, 8] - > [2, 3, 5, 6, 7, 8]

همانطور که مشاهده می کنید با بررسی هر جفت عنصر و در صورت لزوم جابجایی آن ها، لیست ما با استفاده از تکنیک مرتب‌سازی حبابی مرتب شده است.

پیاده‌سازی در کد پایتون

تا اینجای کار تکنیک مرتب‌سازی حبابی را توضیح دادیم. حالا، منطق آن را در کد پایتون پیاده‌سازی خواهیم کرد.

def bubble_sort(list1):  

    for i in range(0,len(list1)-1):  
        for j in range(len(list1)-1):  
            if(list1[j]>list1[j+1]):  
                temp = list1[j]  
                list1[j] = list1[j+1]  
                list1[j+1] = temp  
    return list1  
  
list1 = [5, 3, 8, 6, 7, 2]  
print("The unsorted list is: ", list1)  

print("The sorted list is: ", bubble_sort(list1))  

The unsorted list is:  [5, 3, 8, 6, 7, 2]
The sorted list is:  [2, 3, 5, 6, 7, 8]

بدون استفاده از متغیر موقت (temp variable)

def bubble_sort(list1):  

    for i in range(0,len(list1)-1):  
        for j in range(len(list1)-1):  
            if(list1[j]>list1[j+1]):   
       
                list1[j],list1[j+1] = list1[j+1], list1[j]  
    return list1  
  
list1 = [5, 3, 8, 6, 7, 2]  
print("The unsorted list is: ", list1)  

print("The sorted list is: ", bubble_sort(list1))  

The unsorted list is:  [5, 3, 8, 6, 7, 2]
The sorted list is:  [2, 3, 5, 6, 7, 8]

بهینه‌سازی پیاده‌سازی کد پایتون

می‌توانیم کد بالا را با استفاده از دو تکنیک بهینه‌سازی کنیم. در صورتی که جابه‌جایی‌ها انجام نشود، یعنی لیست مرتب شده است. در تکنیک قبلی، لیست کامل ارزیابی می‌شود، اگرچه به نظر نمی‌آید که این کار ضرور باشد.

می‌توانیم با استفاده از پرچم بولین (Boolean flag) و بررسی این موضوع که آیا در بخش قبلی جابه‌جایی‌هایی انجام شده است یا خیر، از ارزیابی غیرضروری جلوگیری کنیم.

def bubble_sort(list1):  
    has_swapped = True  
  
    while(has_swapped):  
        has_swapped = False  
        for i in range(len(list1) - 1):  
            if list1[i] > list1[i+1]:  
                # Swap  
                list1[i], list1[i+1] = list1[i+1], list1[i]  
                has_swapped = True  
    return list1  
  
  
list1 = [5, 3, 8, 6, 7, 2]  
print("The unsorted list is: ", list1)  
print("The sorted list is: ", bubble_sort(list1))  

The unsorted list is:  [5, 3, 8, 6, 7, 2]
The sorted list is:  [2, 3, 5, 6, 7, 8]

در تکنیک دوم، زمانی که بزرگترین عنصر لیست در انتهای آن قرار می‌گیرد، دور پایان می یابد

در اولین دور، ما بزرگترین عنصر را در موقعیت آخر لیست قرار می‌دهیم و از موقعیت n عبور می‌کنیم. در دومین دور، ما از موقعیت n-1 عبور می‌کنیم که بزرگترین عنصر دوم در لیست است.

در هر دور ، ما می‌توانیم با یک عنصر کمتر از قبل مقایسه کنیم. و در دور k ام، تنها نیاز داریم که در اولین n - k + 1 عنصر مقایسه کنیم.

def bubble_sort(list1):  
    has_swapped = True  
  
    total_iteration = 0  
  
    while(has_swapped):  
        has_swapped = False  
        for i in range(len(list1) - total_iteration - 1):  
            if list1[i] > list1[i+1]:  
                # Swap  
                list1[i], list1[i+1] = list1[i+1], list1[i]  
                has_swapped = True  
        total_iteration += 1  
    print("The number of iteraton: ",total_iteration)  
    return list1  
  
list1 = [5, 3, 8, 6, 7, 2]  
print("The unsorted list is: ", list1)  
# Calling the bubble sort funtion  
print("The sorted list is: ", bubble_sort(list1))  

The unsorted list is:  [5, 3, 8, 6, 7, 2]
The number of iteraton:  6
The sorted list is:  [2, 3, 5, 6, 7, 8]

مقایسه زمان

بیایید مقایسه‌ای بین زمان اجرای کدهای بالا انجام دهیم.

مرتب‌سازی حبابی غیربهینه: 0.0106407

مرتب‌سازی حبابی بهینه: 0.0078251

مرتب‌سازی حبابی با پرچم بولین و لیست کوتاه‌تر: 0.0075207

تمامی تکنیک‌ها برای تعداد کمتری عنصر مفید هستند، اما اگر لیست از تعداد زیادی عنصر تشکیل شده باشد، تکنیک بهینه دوم تفاوت زیادی ایجاد می‌کند.