[알고리즘] 삽입 정렬(Insertion sort) 의 개념 with c++

삽입 정렬이란 자료 배열의 모든 요소를 앞에서 부터 비교하고자 하는 타겟값(tmp)과 정렬된 값을 비교하여 자신의 위치를 찾아 삽입하면서 정렬해나가는 알고리즘이다.

매번 비교할 때마다 앞 부분에 해당하는 범위 모두 타겟값과 비교하여 해당 원소를 삽입할 수 있는 위치를 찾아 배열 위치에 넣는다. 

 

 

 

📌정렬 과정(오름차순)

 

1. 2번째 원소부터 비교 시작한다

2. 이전 위치에 있는 원소들과 타겟이 되는 원소들을 비교한다(타켓 원소는 임시변수에 넣는다)

3. 타겟 원소가 이전 위치에 있던 원소보다 작다면 위치를 바꾼다

4. 이전 데이터도 차례대로 비교하며 정렬해나간다

5. 이 방법을 반복해서 정렬한다

 

 

삽입정렬 예시(wikipedia)

 

 

📌특징

• 구현이 간단하다
• 배열이 길어질수록 효율이 떨어진다
• 선택 정렬이나 버블 정렬과 같은 O(n^2) 알고리즘에 비해 빠르고 안정 정렬이다
• 데이터를 비교하면서 찾아서 비교정렬이다
• 추가적인 공간을 필요하지 않기 때문에 제자리 정렬(in-place-sort)이다
• 데이터를 서로 교환(swap)하면서 임시변수(tmp)가 필요하다

 

 

 

 

 

 

 

 

📌시간 복잡도

- 최선일 경우

• 이동없이 1번씩 비교할 경우
• T(n) = O(n)

- 최악일 경우

• 비교할 때마다 i번씩 비교
• 각 단계마다 원소 이동
• 1+2+3+4+...+(n-1) = n(n-1)/2 번 비교
• T(n) = O(n^2)

 

 

📌삽입 정렬 c++ 코드 구현

#include<stdio.h>

using namespace std;

int main(){

	// 삽입정렬 
	int a[100], n, tmp, i, j;
	scanf("%d", &n);
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
	} 
	for(i=1; i<n; i++){
		tmp=a[i];
		for(j=i-1; j>=0; j--){
			if(a[j]>tmp) a[j+1]=a[j];
			else break;
		}
		a[j+1]=tmp; 
	}
	
	for(i=0; i<n; i++){
		printf("%d ",&a[i]);
	}	
	
	return 0;	
    
}