삽입 정렬(Insertion Sort)
삽입 정렬은 현재 위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 배열 알고리즘입니다.
기본 로직은 아래와 같습니다.
- 삽입 정렬은 두 번째 인덱스부터 시작합니다. 현재 인덱스는 별도의 변수에 저장해주고 비교 인덱스를 현재 인덱스 -1로 잡습니다.
- 별도로 저장해 둔 삽입을 위한 변수와 비교 인덱스의 배열 값을 비교합니다.
- 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해주고, 비교 인덱스를 -1하여 비교를 반복합니다.
- 만약 삽입 변수가 더 크면, 비교 인덱스 +1에 삽입 변수를 저장합니다.
이 정렬 알고리즘은 최악의 경우(역으로 정렬되어있을 경우)엔 n-1개, n-2개,…,1개씩 비교를 반복하여 시간복잡도는 O(n^2)입니다.이미 정렬되어 있는 경우에는 한번씩 밖에 비교를 하지 않아 시간 복답도는 O(n )입니다. 하지만 상한을 기준으로 하는 Big-O notation은 최악의 경우를 기준으로 평가하므로 삽입 정렬의 시간복잡도는 O(n^2)입니다.
이래를 돕기 위해 이미 정렬이 끝난 부분과 앞으로 처리될 대상 범위 사이에 세로선( | )을 넣어서 구분하겠습니다.
| 2 4 5 1 3 // 시작
2 | 4 5 1 3 // 맨 앞에 있는 2는 옮기지 않아도 됩니다.
2 | 4 5 1 3 // 4의 위치를 맞춥니다. 2 바로 다음이므로 위치가 변하지 않습니다.
2 4 | 5 1 3 // 대상 범위를 하나 줄입니다.
2 4 | 5 1 3 // 5의 위치를 맞춥니다. 4바로 다음이므로 이번에도 위치가 그대로입니다.
2 4 5 | 1 3 // 대상 범위를 하나 줄입니다.
2 4 5 | 1 3 // 1의 위치를 맞춥니다.1은 2, 4, 5보다 작으므로 이 값들을 한 칸씩 오른쪽으로 옮긴 다음 비어 있는 공간에 1을 넣습니다.
1 2 4 5 | 3 // 대상 범위를 하나 줄입니다.
1 2 3 4 | 5 // 마지막으로 3의 위치를 맞춥니다.3은 4, 5보다 작으므로 4와 5를 한 칸씩 오른쪽으로 옮긴 다음 비어 있는 공간에 3을 넣습니다.
1 2 3 4 5 | // 대상 범위를 하나 줄입니다. 더는 자료가 없으므로 종료합니다.(최종결과)
