'insert'에 해당되는 글 1건
- 2016.12.08 [Algorithm] About Insertion Sort
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | void InsertionSort(int arrays[], int length) { int key = -1; for(int i=1; i<length; ++i) { key = arrays[i]; // 두번째 값부터. int j=i-1; for(; j>=0; --j) { if(arrays[j] > key) { arrays[j+1] = arrays[j]; } else { break; } } arrays[j+1] = key; } } | cs |
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
'Programing > Algorithm' 카테고리의 다른 글
| [Algorithm] About Quick Sort. (0) | 2016.12.09 |
|---|---|
| [Algorithm] About Select Sort (0) | 2016.12.08 |
| [Algorithm] About Bubble Sort !! (0) | 2016.12.08 |
| [Algorithm] About Linear Search (0) | 2016.12.08 |
| [Algorithm] About Binary Search Algorithm. (0) | 2016.12.08 |
