패스트캠퍼스 온라인 강의

Part1.Ch03-03. 삽입 정렬

삽입정렬이란? (O(N^2))

• 각 숫자를 적절한 위치에 삽입한다.
• 원소가 삽입될 위치를 찾는다. -> 그 위치 도달할 때까지 반복문을 통해 왼쪽으로 이동한다.
• 비효율적인 정렬 알고리즘 (선택, 버블보다 나음)

ㄱ. 첫번째 원소는 정렬 되어있다고 가정한다. (순회한 원소들(왼쪽 원소들)은 정렬되었다고 가정한다.) ㄴ. 둘째 원소를 첫째 원소의 오른쪽으로 둘지 왼쪽으로 둘지 찾는다. ㄷ. 셋째가 첫째 원소와 둘째 원소 앞과 뒤중 어느 곳에 둘지 찾는다. ㄹ. 반복한다.

즉, N번 반복한다. 그런데, break(적절한 위치가 맨 앞에까지 가지 않아도 되는 상황) 덕에 최선 복잡도는 O(N)이 되기에 선택정렬과 버블정렬보다 낫다. (선형탐색)