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

index 0 1 2 3 4 5 6 7 8 9
value 5 3 8 1 2 4 7 6 9 0

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.

index 0 1 2 3 4 5 6 7 8 9
value 1 3 5 8 2 4 7 6 9 0

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. ..

Recommended Posts

Insertion sort
Insertion sort implementation
visualize insertion sort
sort
Insertion sort of AOJ exercises
Selection Sort
[Python] Sort
Natural sort
Python # sort
Bubble sort
Bubble sort
Algorithm learned with Python 16th: Sorting (insertion sort)
Merge Sort Explained
Hands-on sleep sort
Sort by pandas
Bubble sort, selection sort, insertion sort, shell sort, merge sort, quick sort, count sort (Python)