[PYTHON] Insertion sort

Starting today [INTRODUCTION TO ALGORITHMS](https://www.amazon.co.jp/Introduction-Algorithms-Thomas-H-Cormen/dp/8120340078/ref=sr_1_2?__mk_ja_JP=Katakana &keywords=introduction+to+algorithm&qid=1581077652&sr8 Since I started reading -2), there are many simple contents, but I will summarize the algorithm.

Insertion sort

Sorting an array with 10 elements by insertion sort is similar to the following example.

There are 10 playing cards on the table, and the number of cards in your hand is 0 at the beginning. I draw cards from the table one by one and add them to my hand, but I always keep my hand sorted in ascending order. You want to keep your hand tidy, like a card with a small number on the left and a card with a large number on the right. The point of this process is that ** cards can be classified into three types **.

--Already sorted cards in your hand ――The card you are about to add by pulling it from the table --Cards still on the table

Insertion sort also pays attention to this.

--The part of the array that has already been sorted in ascending order --The element you are looking at in the array --The part of the array that has not yet been sorted in ascending order

For example

Suppose you have an array with 10 elements. Think of it as having all the cards still on the table. Suppose you draw one card at a time and you just draw the fifth one. This is equivalent to the array being sorted up to index 0-3 and now focusing on index 4-2.

Now, let's find the position to insert this 2.

――Comparing 2 and 8, 8 is larger, so replace the positions of 2 and 8. ――Comparing 2 and 5, 5 is larger, so exchange the positions of 2 and 5. ――Comparing 2 and 3, 3 is larger, so replace the positions of 2 and 3. ――Comparing 2 and 1, 2 is larger, so it ends here.

Do the same for the 6th to 10th cards to get a sorted array. This is the procedure for insertion sort.

def insertion_sort(a) -> None:
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while key < a[j] and j >= 0:
            a[j+1] = a[j] 
            j -= 1
        a[j+1] = key

a = [1, 3, 5, 8, 2, 4, 7, 6, 9, 0]
insertion_sort(a)
print(a)

output

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

The text I introduced at the beginning explains various things about one algorithm, such as why you can divide pages so much with insertion sort, so I will write another article if there is something to read and supplement. ..