Insertion Sort

[Algorithm] Insertion Sort(삽입 정렬) 1. 정의 2번째 원소부터 시작하여 그 앞의 원소들과 대소비교하여 삽입할 위치를 결정하여 삽입 Selection Sort와 유사하지만, 좀 더 효율적인 알고리즘 시간복잡도 최선 : $O(n)$ → 모두 다 정렬되어 있을 경우 평균 : $O(n^2)$ 최악 : $O(n^2)$ 2. 동작 과정(오름차순) 2번째 인덱스 값을 tmp에 저장 tmp 앞에 있는 원소들과 비교하여 가장 알맞은 자리(arr[i] < arr[tmp] < arr[i + 1])에 삽입 → 삽입하는 자리는 뒤로 한칸씩 밀린다. 1번으로 돌아가 반복 3. 장단점 장점 알고리즘이 단순 정렬되어 있을 경우 매우 효율적 제자리 정렬 안정 정렬 단점 평균과 최악의 시간복잡도가 $O(n^2)..