Algorithm learned with Python 16th: Sorting (insertion 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 16th bullet.

Insertion sort

It is assumed that the data has been sorted in order from the top of the list, and the data next to it is used as the inserted data. Then, the location of the inserted data in the sorted data is compared in order from the end of the sorted data, and if necessary, the data is replaced and moved to the desired position. The image is shown below.

As shown in the above figure, you can see how the sorted data is gradually sorted in ascending order in a way that expands it.

Implementation

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

code

insert_sort.py

"""
2021/01/09
@Yuya Shimizu

Insertion sort
"""

def insert_sort(data):
    """Insertion sort: Expand the sorted parts little by little and sort them in ascending order."""
    #Examine the inserted data one by one
    for i in range(1, len(data)):
        temporary = data[i]         #Temporarily record insert data
        j = i - 1
        while (j >= 0) and (data[j] > temporary):   #If the inserted data is smaller than the data in the sorted data and is to the right, it will be replaced repeatedly.
            data[j + 1] = data[j]       #Move one data to the right
            j -= 1
        data[j + 1] = temporary     #Substitute the inserted data that was temporarily recorded at the place where the movement was completed by the above operation

    return data


if __name__ == '__main__':
    DATA = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13]

    sorted_data = insert_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 insert_sort (DATA).

Computational complexity of insertion sort

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) $ **.

Impressions

Continuing from the last time, it wasn't that complicated. I learned that it would be possible to sort from the back. 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