Algorithm learned with Python 17th: Sorting (bubble sort)

#Algorithm learned in Python

Introduction

Implement the basic algorithm in Python to deepen your understanding of the algorithm. Insertion sort is handled as the 17th bullet.

Bubble sort

Generally speaking, exchange sort refers to bubble sort. Compare the adjacent data in the list, and if the order of magnitude is different, arrange them. The image is shown below.

Implementation

The code of the program according to the previous procedure and the output at that time are shown below.

code

bubble_sort.py

"""
2021/01/10
@Yuya Shimizu

Bubble sort
"""

def bubble_sort(data):
    """Bubble sort: Compares and sorts two data from the front."""   
    for i in range(len(data)):
        for j in range(len(data) - i -1):
            if data[j] > data[j+1]: #If the left side is larger
                data[j], data[j+1] = data[j+1], data[j] #Swap back and forth
                
    return data

if __name__ == '__main__':
    DATA = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
    sorted_data = bubble_sort(DATA.copy())

    print(f"{DATA}  →  {sorted_data}")

output

[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]  →  [2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

It has been replaced successfully, but with this, even if comparison replacement is no longer necessary in the middle, it will always be repeated for the number of data. In order to omit that part, we added an operation to exit the repetition when the replacement is not performed after one round. The code and output are shown below.

code

bubble_sort_improved.py

"""
2021/01/10
@Yuya Shimizu

Bubble sort (improved version)
"""

def bubble_sort(data):
    """Bubble sort: Compares and sorts two data from the front. However, omit the parts that do not need to be replaced anymore."""
    change = True   #Assuming there is room for exchange
    
    for i in range(len(data)):
        if not change:  #Escape repeatedly without room for replacement
            break
        change = False  #Assuming there is no room for exchange
        for j in range(len(data) - i -1):
            if data[j] > data[j+1]: #If the left side is larger
                data[j], data[j+1] = data[j+1], data[j] #Swap back and forth
                change = True #There may be room for exchange
                
    return data

if __name__ == '__main__':
    DATA = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
    sorted_data = bubble_sort(DATA.copy())

    print(f"{DATA}  →  {sorted_data}")

output

[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]  →  [2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

You can see that they are sorted in ascending order. This time, I want to compare before and after sorting, so I dare to store the result in the variable sorted_data, and the argument to the function is DATA.copy () by the copy function. The arguments are not affected. If you just want to sort, you don't need to do that, just use bubble_sort (DATA).

Bubble sort computational complexity

Finally, I will touch on the amount of calculation. Basically, as with selection sort, ** the amount of calculation is $ O (n ^ 2) $ ** when expressed in order notation. However, if no exchange occurs, only comparison (no exchange) is required, so ** $ O (n) $ **. The worst time complexity is still $ O (n ^ 2) $.

Impressions

Continuing from the last time, it wasn't that complicated. I learned that when swapping in a list at once, it is not necessary to temporarily save the value, just substitute it with a comma as follows. I think I got a big one.

data[j+1], data[j] = data[j], data[j+1]

I am looking forward to the sorting algorithm from the next time onward.

References

Introduction to algorithms starting with Python: Standards and computational complexity learned with traditional algorithms Written by Toshikatsu Masui, Shoeisha