Algorithm learned with Python 15th: Sorting (selection sort)

#Algorithm learned in Python

Introduction

Implement the basic algorithm in Python to deepen your understanding of the algorithm. The 15th bullet is the selection sort. From this time, we will learn the algorithm for sorting for a while.

Why learn sorting algorithms?

・ Library is generally used, but it is important to know its ** implementation ** ・ There are many parts where the idea of ​​sorting is ** helpful when creating other programs ** ・ Not only can you learn the basics of programming such as loops, conditional branching, list handling, function creation, and recursive calls, but also ** an ideal problem that shows the necessity of comparing computational complexity ** -Each process is simple, it does not take much time to implement, and it is a ** practical program **.

Selection sort

Find the minimum value in the list and swap the minimum value with the beginning. Then, using the second as a reference, find and replace the minimum value excluding the beginning. By repeating this, it is possible to sort in ascending order (smallest order). The image is shown below. As shown in the above figure, it can be seen that sorting can be done in ascending order by changing the criteria for replacement with the minimum value.

Implementation

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

code

select_sort.py

"""
2021/01/07
@Yuya Shimizu

Selection sort
"""

def select_sort(data):
    """Selection sort: Sort by ascending order by swapping values ​​and locations smaller than yourself"""
    for i in range(len(data)):
        Min = i     #Set the replacement target
        for j in range(i+1, len(data)):
            #If there is a value smaller than the set value, record that position as the minimum value.
            if  data[j] < data[Min]:
                Min = j
        #Swap the current position and the minimum value ⇒ As a result, arrange in ascending order from the left
        data[i], data[Min] = data[Min], data[i]
        
    return data     #Returns the sorted data

if __name__ == '__main__':
    DATA = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
    sort = select_sort(DATA.copy())     #Take a copy as an argument so that the list does not change for later comparison

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

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 a variable called sort, and use the copy function as an argument to the function like DATA.copy (). The arguments are not affected. If you just want to sort, you don't need to do that, just use select_sort (DATA).

Computational complexity of selection sort

Finally, I will touch on the amount of calculation. Finding the first minimum value requires comparison with the remaining $ n-1 $ elements, as well as $ n-2 $ times and $ n-3 $ for the second and third. It is necessary to compare the times. Therefore, the total number of comparisons is $ (n-1) + (n-2) + ... + 1 = \ frac {n (n-1)} {2} $. $ \ frac {n (n-1)} {2} = \ frac {1} {2} n ^ 2-\ frac {1} {2} n $, but when $ n $ becomes large, the first term On the other hand, the second term is sufficiently small and can be ignored, so the complexity is $ O (n ^ 2) $ ** when expressed in order notation.

Impressions

There was nothing particularly difficult, and I felt that it would be possible to review the past. This time, the first sort is a selection sort, so it cannot be compared with others, but I am looking forward to other sorting algorithms that I will learn from now on, and my morale will be enhanced. I also feel that I have become accustomed to order notation.

References

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