목록Insertion Sort (1)

서두르지 말고 쉬지 말자

[정렬] 삽입 정렬 (Insertion Sort)

삽입 정렬 설명두 번째 요소를 선택한다.그 값을 key로 저장해서, 그 앞에 있는 요소들과 크기 비교한다.앞쪽 값(들)이 key보다 크면, 한 칸씩 오른쪽으로 복사(밀기)한다.key값이 들어가야 할 위치가 나오면, 그 자리에 key를 삽입한다.이를 n-1번째(마지막) 요소까지 반복한다시간복잡도최선의 경우 : 매번 한번씩만 비교 시 -> O(n) 최악의 경우 : 1 + 2 + 3 + .... + (n-2) + (n-1) = n(n-1)/2 이므로 -> O(n^2)장점 요소들의 수가 적으면 알고리즘이 단순해서 다른 복잡한 정렬 알고리즘보다 유리어느정도 요소들이 정렬되어 있으면 시간 단축됨단점요소들의 수가 많은 경우에 적합하지 않음다른 알고리즘들에 비해 요소의 이동이 잦음
코딩 공부/Algorithm 2025. 7. 17. 16:10
이전 Prev 1 Next 다음