Insert algorithm (Insertion Sort)

Sort insertion is a sorting algorithm based on in-place comparison. Here, a sub-list is always maintained in sorted form. Inserting is inserting an element into the sorted list of children. The element is inserted in the appropriate position so that the list is still in order.

What is sort insertion (Insertion Sort)?

With the array data structure, we imagine that: the array consists of two parts: a sorted list of children and the other part are unordered elements. The insertion sort algorithm will perform a continuous search through that array, and unordered elements will be moved and inserted into the appropriate position in the sub-list (of the same array).

This algorithm is not suitable for use with large data sets when the case complexity is worst and the average case is Ο (n2) where n is the number of elements.

How to solve the insertion arrangement?

For example, we have an array of unordered elements:

Insert algorithm (Insertion Sort) Picture 1 Insert algorithm (Insertion Sort) Picture 1

The insertion sort algorithm compares the first two elements:

Insert algorithm (Insertion Sort) Picture 2 Insert algorithm (Insertion Sort) Picture 2

The algorithm found that both 14 and 33 were in ascending order. Now, 14 is in the sorted list of children.

Insert algorithm (Insertion Sort) Picture 3 Insert algorithm (Insertion Sort) Picture 3

The insertion algorithm continues to move to the next element and compares 33 and 27.

Insert algorithm (Insertion Sort) Picture 4 Insert algorithm (Insertion Sort) Picture 4

And see that 33 is not in the right position.

Insert algorithm (Insertion Sort) Picture 5 Insert algorithm (Insertion Sort) Picture 5

Algorithm to insert and swap positions of 33 and 27. Also check all elements in the sorted list. Here, we see that in this sub-list only one element 14 and 27 is greater than 14. Therefore the sub-list remains the same after the swap.

Insert algorithm (Insertion Sort) Picture 6 Insert algorithm (Insertion Sort) Picture 6

Now in the list of children we have two values 14 and 27. Continue to compare 33 with 10.

Insert algorithm (Insertion Sort) Picture 7 Insert algorithm (Insertion Sort) Picture 7

These two values are not in order.

Insert algorithm (Insertion Sort) Picture 8 Insert algorithm (Insertion Sort) Picture 8

So we swap them.

Insert algorithm (Insertion Sort) Picture 9 Insert algorithm (Insertion Sort) Picture 9

Swapping leads to 27 and 10 in no order.

Insert algorithm (Insertion Sort) Picture 10 Insert algorithm (Insertion Sort) Picture 10

So we also exchange them.

Insert algorithm (Insertion Sort) Picture 11 Insert algorithm (Insertion Sort) Picture 11

We see again that 14 and 10 are not in order.

Insert algorithm (Insertion Sort) Picture 12 Insert algorithm (Insertion Sort) Picture 12

And we continue to swap these two numbers. Finally, after the third loop we have 4 elements.

Insert algorithm (Insertion Sort) Picture 13 Insert algorithm (Insertion Sort) Picture 13

The above process will continue until all unordered values are sorted into the sorted child list.

Next we explore the programming aspect of insertion sorting algorithm.

Insert algorithm (Insertion Sort)

From the above illustration, we have a general picture of the insertion arrangement algorithm, from which we will have the basic steps in the algorithm as follows:

 Bước 1 : Kiểm tra nếu phần tử đầu tiên đã được sắp xếp. trả về 1 Bước 2 : Lấy phần tử kế tiếp Bước 3 : So sánh với tất cả phần tử trong danh sách con đã qua sắp xếp Bước 4 : Dịch chuyển tất cả phần tử trong danh sách con mà lớn hơn giá trị để được sắp xếp Bước 5 : Chèn giá trị đó Bước 6 : Lặp lại cho tới khi danh sách được sắp xếp

Sample algorithm for arranging foam

 B ắ t đầ u h à m insertionSort ( A : m ả ng ph ầ n t ử ) int holePosition int valueToInsert for i = 1 t ớ i length ( A ) th ự c hi ệ n : /* chọn một giá trị để chèn */ valueToInsert = A [ i ] holePosition = i /*xác định vị trí cho phần tử được chèn */ while holePosition > 0 v à A [ holePosition - 1 ] > valueToInsert th ự c hi ệ n : A [ holePosition ] = A [ holePosition - 1 ] holePosition = holePosition - 1 k ế t th ú c while /* chèn giá trị tại vị trí trên */ A [ holePosition ] = valueToInsert k ế t th ú c for K ế t th ú c h à m

According to Tutorialspoint

Previous lesson: Bubble Sort (Bubble Sort)

Next lesson: Selection sort algorithm (Selection Sort)