::GameDeveloperPlayground::

Hello, i am GameDeveloperPlayground.

I am a Korean student and I post it for English practise.

I would appreciate pointing out grammar or typos.

In this posting in Inserting Sort.

About Insertion Sort

Insertion sort is an algorithm that compares all the element of data array with parts of array that have already been sorted from the first to the last.

In the case of Insertion Sort, the first element is already aligned. And start sorting.

Unsorted elements ar insered at the appropriate position relative to the sorted list starting with the last element in the list.

Repeat this operation until all elements ar sorted.

Sorting process

Show you a simple insertion sort example.

5 numbers are given as below, will sort by insertion sort.

4 9 2 5 7

Insertion sort determines that the first element is aligned and starts from the second.

First

4 / □ 2 5 7  | key value = 9

9 is greater than 4 and is located behind 4. 4 □ 2 5 7 

4 / 9 2 5 7 

Second

4 9 / □ 5 7 | key value = 2

2 is less than 9, so it is located in front of 9. 4 □ 9 5 7 

2 is less than 4, so it is located in front of 4. □ 4 9 5 7

2 4 / 9 5 7

Third

2 4 9 / □ 7 | key value = 5

5 is less than 9, so it is located in front of 9. 2 4 □ 9 7

5 is greader than 4, so it is located behind 4. 2 4 □ 9 7

2 4 5 / 9 7

fourth

2 4 5 9 / □ | key value = 7

7 is less than 9, so it is located in front of 9. 2 4 5 □ 9

7 is greater than 5, so it is located behind 5. 2 4 5 □ 9

2 4 5 7 9

Sorting is complete.

(Source : 나무위키 삽입정렬)

Example Code

It is Simple.

Algorithm analysis

Number of comparisons.

Insertion Sort is from the second element to the first element, than the third element is compared to the second and first.

Of course, if it's already sorted, will not compare.But it is worst case.

0 + 1 + 2 + 3 .... + n-2 + n-1 = n(n-1)/2

So in the worst case, the time complexity is O(N²).

In the best case, the comparison is O(N).

Below is the data I found when I searched for Insertion sort.

Insertion Sort Image Example.

( Source : 위키 백과 : 삽입 정렬 )

Example video of Insertion Sort.

Source ( 유투브 동영상(클릭) )

Thank you