삽입 정렬이란? 이미 정렬된 부분에서 새로운 요소가 들어갈 위치를 찾아 넣음 시간복잡도 시간 복잡도 (comparisons) 시간 복잡도 (swaps) 최악 O(n^2) O(n^2) 평균 O(n^2) O(n^2) 최상 O(n) O(1) 공간 복잡도 전체 O(n), 보조 O(1) 특징 안정 정렬(Stable Sort) 제자리 정렬(In-place Sort). 추가메모리 x 대부분 정렬된 상태일때는 빠름(요소가 적을때도 빠른편) 반대로 요소가 많을 경우 느려짐 로직 이중 for문으로 순회 index 1부터 실행. 해당 index의 왼쪽 부분의 배열에서 본인이 들어갈 위치를 찾아 넣음 예시 (오름차순의 경우) [3,5,1,2] 일 때 index 1인 5가 왼쪽의 3 보다 큰 수이므로 그대로 둔다 -> [3,5..