[JS] 삽입 정렬

1. 삽입 정렬 삽입 정렬은 선택 정렬, 버블 정렬과 함께 시간복잡도 $$ O(n^2) $$ 을 가진다. 하지만 삽입 정렬은 선택정렬, 버블 정렬과 같은 시간복잡도를 가지지만, 두 정렬보다는 빠른 속도를 가진다. 그 이유는 선택, 버블 정렬의 경우에는 일일히 원소 값을 비교하는 탐색 과정을 거치지만, 삽입 정렬의 경우, 필요할 때만 위치를 바꾸는 방식을 이용하기 때문이다. 「자바로 배우는 쉬운 자료구조, 한빛 미디어」 책에서는 S(정렬 되어있는 부분집합), U(정렬되지 않은 부분집합)으로 나누어서 U의 원소를 하나씩 꺼내서 이미 정렬되어 있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입하는 방식을 이용한다고 설명하지만, 결국 의미는 같다. 음, 그러니까 그냥 필요할 때만 위치를 바꾼다. 라..

2020.05.31