Insertion Sort

1. Input : A[N]

  - A : Array

  - N : The Number of total Elements

 

2. Input Example 

3

5

2

1

7

6

4

 

3. Result

1

2

3

4

5

6

7

 

4. pseudo code

for i =1 to N-1

key = A[i];

for j=i-1 to 0

if A[j]> key 

A[j+1] = A[j];

else

break;

A[j+1]=key ;

 

 

5. Complexity Analysis

  모든 원소 N 에 대해 2번 for 문을 동작하므로 N^2 의 복잡도를 갖는다.

 (For all element N, 2-times for statement is required. So it has a complexity with O(N^2) )