단순 삽입 정렬

단순 삽입 정렬 

 

• 선택한 요소를 더 앞쪽의 알맞은 위치에(오름차순이든, 내림차순이든) 삽입하는 작업을 반복하여 정렬한다 
• 2번째 요소. index[1] 값부터 진행한다 
• 요소들이 서로 뒤바뀌지 않아 안정적이다 
• 교환 횟수는 n^2/2 이다
• 시간복잡도가 O(n^2)라서 효율성이 떨어진다

 

코드예시

 

for(int i=1; i<n; i++) {

			int j;
			
            //target 값에 a[i]부여
			int tmp = a[i];

			for(j=i; j>0 && a[j-1] > tmp; j--) {
				//값을 교환함
				a[j] = a[j-1];

			}
		 //j--에 따라서 한 칸 앞에 a[i]인 tmp 값을 삽입해줌 
			a[j] = tmp;

		}

	}

 

10

4

2

11

3

20

15

과정

 

1) tmp = a[1]인 4가 된다

2) 조건이 맞기에 a[1] = a[0]인 10이 된다 

3) j를 1 감소시켜 j=0이 된다

4) a[0] 은 타겟값 4가 된다 

 

결과 

 

4

10

2

11

3

20

15

4와 10이 바뀐다. 이와 같은 과정을 계속하면 된다