삽입정렬(InsertionSort)
최악의 경우 버블정렬과 같이 n^2 의 시간복잡도를 가진다. 최선의 경우 정렬되어 있는 경우 n의 시간복잡도를 가진다. 평균 버블정렬보다 절반정도의 빠름을 보여준다. 특정위치에(인덱스)있는 요소를 적절한 위치에 들어갈 수 있도록 되어있다. 해당 인덱스는 버블정렬과 다르게, 선택되어진 특정 값이 자신의 위치를 찾는순간 더 이상 앞의 데이터와 비교할 필요(정확히 스위칭)가 없어지기 때문에 효과적이다. 예 제 Ex) 5 3 6 4 1) 2번째 3이 선택되어 진 값 ㅁ 5 6 4
