48. 삽입정렬

삽입정렬이란?

삽입정렬은 간단하면서 효율적인 정렬 알고리즘 중 하나이다.

요소를 적절한 위치에 삽입하면서 정렬된 부분을 확장해 나가는 방식으로 동작한다.

 

동작 방식

1. 주어진 리스트를 정렬된 부분과 정렬되지 않은 부분으로 나뉜다.

2. 첫 번째 요소만 정렬된 부분에 속하고 나머지 요소들은 정렬되지 않은 부분에 속한다.

3. 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분에 올바른 위치에 삽입한다.

4. 정렬된 부분을 확장하여 삽입한 요소를 포함하도록 한다.

5. 위 과정을 정렬되지 않은 부분이 더이상 없을 때까지 반복한다.

 

삽입 정렬은 선택정렬과 버블정렬과는 달리, 정렬된 부분을 순차적으로 확장해 가면서 정렬을 수행하기 때문에 비효율적이다. 최선의 경우 이미 정렬된 리스트에서는 비교 연산이 필요하지 않고, 시간복잡도가 O(n)이다. 평균 및 최악의 경우에는 시간복잡도가 O(n^2)이다.

---

// 삽입정렬
void insertsort(int User_Data[], int n){
	int i, temp, j;
    
	// 시작 인덱스가 0이므로 for문 시작이 1이다. 
	for(i=1; i<n; i++) {
		temp = User_Data[i];
        for(j=i-1; j>=0 && temp < User_Data[j]; j--)
			User_Data[j+1] = User_Data[j];
		
		User_Data[j+1] = temp;
    }
}