삽입 정렬은 가장 기초적이고 쉬운 정렬 알고리즘입니다.
- 배열의 두 번째 성분부터 시작합니다. 첫 번째 성분은 이미 정렬된 부분 배열의 시작점으로 간주합니다. 이 두 번째 성분을 **key(키)**로 지정합니다.
- key 값과 정렬된 부분 배열을 비교합니다. key 값보다 큰 요소가 있는지 확인하기 위해 정렬된 부분 배열(key의 왼쪽 부분)의 끝에서부터 역순으로 탐색합니다.
- 요소들을 한 칸씩 뒤로 밀어냅니다. 만약 key 값보다 큰 요소를 발견하면, 그 요소를 오른쪽으로 한 칸 이동시켜 key가 삽입될 공간을 만듭니다. 이 과정은 key 값보다 작거나 같은 요소를 만날 때까지 반복됩니다.
5 > 3 (True): 5를 한 칸 뒤로 밀어 냅니다.3 > 5 (False): 3은 5보다 작으므로 멈춥니다.
- key를 올바른 위치에 삽입합니다. 모든 비교와 이동이 끝난 후, key를 비워진 위치에 삽입합니다.
- 다음 성분으로 넘어갑니다. 다음 미정렬된 배열의 성분을 새로운 key로 지정하고, 이 과정을 배열의 마지막 성분까지 반복합니다. 이 과정을 통해 배열 전체가 정렬됩니다.
시간복잡도
Bset: O(N)
Worst: O(N^2)