삽입 정렬(Insertion Sort)

🟩 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입

왼쪽에는 정렬이 끝난 수가 오게되고, 오른쪽에는 아직 확인하지 않은 숫자가 남게 되는데, 오른쪽 미탐색 영역에서 숫자를 하나 꺼내어 정렬이 끝난 영역의 적절한 위치에 삽입해 나가는 방식

 

이미 정렬이 되어있다면 필요없이 종료한다.

InsertionSort(A[ ], n) {
	for (i=1; i< n; i++) { // A[0] 정렬 부분; 1, ⋯, (n-1)까지 (n-1)번 반복
		val= A[i]; // 미정렬 부분 A[i..n-1]의 첫 번째 데이터 선택
		for (j=i; j > 0 && A[j-1] > val; j--) // 삽입할 위치 찾기
			A[j] = A[j-1]; // 정렬 부분의 A[j-1]이 크면 뒤로 한 칸 이동
		A[j] = val; // 찾아진 위치에 선택된 데이터 삽입
	}
	return (A);
}

 

🌟 내림차순으로 정렬할 경우 내부 반복문의 조건을 아래와 같이 변경한다.

for(j=i; j > 0 && A[j-1] < val; j--)

 

🟩 시간 복잡도

바깥 루프 i	1	2	3	...	n-1
루프 j의 비교 횟수	1	2	3	...	n-1

 

총 비교 횟수 = 1 + 2 + ... + (n-2) + (n-1) = n(n-1)/2

👉 O(n^2)

cf. 이미 정렬된 상태인 경우 O(n)