[알고리즘] 삽입정렬(InsertionSort)

[ 삽입정렬 ]

삽입정렬 InsertSort는정렬대상을 두 부분으로 나눠서

정렬 안 된 부분에 있는 데이터를
정렬 된 부분의 특정 위치에 "삽입" 해가면서

정렬을 진행하는 알고리즘임.

따라서 삽입정렬을 해나가는 과정 속에서 정렬대상은
"정렬이 완료된 부분" 과 "정렬 안 된 부분"으로 나뉘게 됨.

왼쪽에서부터가 정렬부분이고 오른쪽에서부터가 정렬 안된 부분임.
왼쪽에서 오른쪽이 정렬 방향이니깐

 

void InsertSort(int arr[], int N) {
	int k;
	for (int i = 1; i < N; i++) {
		int key = arr[i];
		for (k = i-1; k >=0; k--) {
        	// 뒤에서부터 큰 놈들 한 칸씩 오른쪽으로 땡겨주기
			if (key < arr[k]) {
				arr[k+1] = arr[k];
			}
			else {
            			arr[k] = key;
				break;
			}
		}
	}
}

 

정렬할 자료를 두 개의 부분집합 S와 U로 가정 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소.

 

코드에서는 정렬할값(key)를 미리 빼내고 자리 찾을때까지 S원소를 한칸씩 밀어주기.

 

자리찾으면 key 대입하고 한턴 종료

 

int main() {
	// int arr[6] = { 5,2,1,4,3,6 };
	int arr[6] = { 4,2,1,7,3,5};
	InsertSort(arr, 6);
	for (int i = 0; i < 6; i++) printf("%d ", arr[i]);
	return 0;
}

 

 

---

[ 시간복잡도 ]

[ 점화식 계산 ]

최악일때 과연 몇 번의 비교연산을 더 진행해야할까

다음과 같이 정렬되어 있는 배열에 한 개의 원소가 추가되면
최악의 경우 N-1번의 추가비교연산이 진행된다.
( 최악의 경우 == 제일 작은 수가 추가로 들어올때 )