삽입 정렬 (Insertion Sort)
: 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 하나씩 꺼내면서 알맞은 자리에 삽입해 나가는 방식
- 선택 정렬과 마찬가지로 정렬된 영역과 정렬되지 않은 영역으로 나눠서 계산함
- 정렬되지 않은 영역에서 데이터를 꺼내서 정렬된 영역 내 적절한 위치에 삽입해서 정렬함
선택 정렬의 성능
- 시간 복잡도: O(n²)
- 성능이 좋지 않음
선택 정렬의 장단점
장점
- 이해와 구현이 간단함
단점
- 성능이 O(n²)으로 별로 좋지 않음
삽입 정렬 흐름
[ 4, 1, 5, 3, 6, 2 ]
- 정렬된 영역: 4, 정렬되지 않은 영역: 1, 5, 3, 6, 2
- 정렬되지 않은 영역의 첫 번째 원소인 1을 정렬된 영역의 마지막 데이터인 4와 비교함
- 4는 1보다 크기 때문에 4를 오른쪽 인덱스에 덮어씀([ 4, 4, 5, 3, 6, 2 ])
- 삽입할 데이터 1을 정렬된 영역의 다른 데이터와 비교하려는데 더 이상의 데이터가 없으므로 마지막에 비교한 데이터 4 위치에 1을 삽입함([ 1, 4, 5, 3, 6, 2 ])
[ 1, 4, 5, 3, 6, 2 ]
- 정렬된 영역: 1, 4, 정렬되지 않은 영역: 5, 3, 6, 2
- 정렬되지 않은 영역의 첫 번째 원소인 5를 정렬된 영역의 마지막 데이터인 4부터 역순으로 비교함([ 1, 4, 5, 3, 6, 2 ])
- 4는 5보다 작으므로 따로 덮어쓰지 않음
- 5는 현재 자리에 그대로 있음([ 1, 4, 5, 3, 6, 2 ])
[ 1, 4, 5, 3, 6, 2 ]
- 정렬된 영역: 1, 4, 5, 정렬되지 않은 영역: 3, 6, 2
- 정렬되지 않은 영역의 첫 번째 원소인 3을 정렬된 영역의 마지막 데이터인 5부터 역순으로 비교함
- 5는 3보다 크기 때문에 5를 오른쪽 인덱스에 덮어씀([ 1, 4, 5, 5, 6, 2 ])
- 삽입할 데이터 3을 정렬된 영역의 5의 이전 데이터 4와 비교함
- 4는 3보다 크기 때문에 4를 오른쪽 인덱스에 덮어씀([ 1, 4, 4, 5, 6, 2 ])
- 삽입할 데이터 3을 정렬된 영역의 4의 이전 데이터 1과 비교함
- 1은 3보다 작으므로 따로 덮어쓰지 않음([ 1, 4, 4, 5, 6, 2 ])
- 3을 마지막으로 비교했던 1의 다음 인덱스에 덮어씌움([ 1, 3, 4, 5, 6, 2 ])
[ 1, 3, 4, 5, 6, 2 ]
- 정렬된 영역: 1, 3, 4, 5, 정렬되지 않은 영역: 6, 2
- 정렬되지 않은 영역의 첫 번째 원소인 6을 정렬된 영역의 마지막 데이터인 5부터 역순으로 비교함
- 5는 6보다 작으므로 따로 덮어쓰지 않음
- 6는 현재 자리에 그대로 있음([ 1, 3, 4, 5, 6, 2 ])
- 정렬되지 않은 영역의 첫 번째 원소인 2을 정렬된 영역의 마지막 데이터인 6부터 역순으로 비교함
- 6은 1보다 크기 때문에 6을 오른쪽 인덱스에 덮어씀([ 1, 3, 4, 5, 6, 6 ])
- 삽입할 데이터 2을 정렬된 영역의 6의 이전 데이터 5와 비교함
- 5는 2보다 크기 때문에 5를 오른쪽 인덱스에 덮어씀([ 1, 3, 4, 5, 5, 6 ])
- 삽입할 데이터 2을 정렬된 영역의 5의 이전 데이터 4와 비교함
- 4는 2보다 크기 때문에 4를 오른쪽 인덱스에 덮어씀([ 1, 3, 4, 4, 5, 6 ])
- 삽입할 데이터 2을 정렬된 영역의 4의 이전 데이터 3과 비교함
- 3은 2보다 크기 때문에 3를 오른쪽 인덱스에 덮어씀([ 1, 3, 3, 4, 5, 6 ])
- 삽입할 데이터 2을 정렬된 영역의 3의 이전 데이터 1과 비교함
- 1은 2보다 작으므로 따로 덮어쓰지 않음
- 2를 마지막으로 비교했던 1의 다음 인덱스에 덮어씌움([ 1, 2, 3, 4, 5, 6 ])
결과: [ 1, 2, 3, 4, 5, 6 ]
예시: 무작위 배열 정렬하기
- for문의 i가 1부터 시작하는 이유는 첫 번째 원소(0번째 인덱스)는 이미 정렬되어 있다고 가정하기 때문
(i == 0은 정렬된 영역의 첫 번째 요소) - i 인덱스에 해당하는 원소는 정렬되지 않은 영역의 첫 번째 원소이기 때문에 변수에 저장해야 함
- 정렬된 영역의 마지막 원소(j-1)는 정렬되지 않은 원소의 첫 번째 원소(i)의 한 칸 앞
let arr = [4,1,5,3,6,2];
function InsertionSort(arr){
for(let i = 1; i < arr.length; i++){
let insertingData = arr[i];
let j; // 삽입 위치(삽입할 원소보다 작은 원소의 인덱스 저장)
for(j = i - 1; j >= 0; j--){ // 정렬된 영역의 뒤부터 역순으로 순회하며 정렬될 원소의 삽입 위치를 찾는 부분
if(arr[j] > insertingData){ // 현재 순회하는 인덱스의 원소가 삽입할 원소보다 크면
arr[j + 1] = arr[j]; // 오른쪽 인덱스에 덮어씀
}else{
break;
}
}
// 삽입할 원소의 위치가 정해짐
arr[j + 1] = insertingData; // 원소 삽입
}
}
console.log("===== 정렬 전 =====");
console.log(arr); // [ 4, 1, 5, 3, 6, 2 ]
InsertionSort(arr);
console.log("===== 정렬 후 =====");
console.log(arr); // [ 1, 2, 3, 4, 5, 6 ]
실행 흐름
- 1회전 (i = 1) 👉 바깥 반복문
- 바깥 반복문 i = 1 → insertingData = 1
- j = 0 → arr[0] = 4 > 1 → 오른쪽으로 한 칸 밀기 → [4, 4, 5, 3, 6, 2]
- j = -1 → 반복문 종료
- arr[j+1] = arr[0]에 1 삽입 → [1, 4, 5, 3, 6, 2]
➡️ 1이 4 앞에 들어가면서 앞 두 원소가 정렬됨
- 2회전 (i = 2) 👉 바깥 반복문
- 바깥 반복문 i = 2 → insertingData = 5
- j = 1 → arr[1] = 4 > 5? No → 반복문 종료
- arr[j+1] = arr[2]에 5 삽입 (자리 그대로) → [1, 4, 5, 3, 6, 2]
➡️ 5는 이미 제자리에 있음 (변경 없음)
- 3회전 (i = 3) 👉 바깥 반복문
- 바깥 반복문 i = 3 → insertingData = 3
- j = 2 → arr[2] = 5 > 3 → 오른쪽으로 한 칸 밀기 → [1, 4, 5, 5, 6, 2]
- j = 1 → arr[1] = 4 > 3 → 오른쪽으로 한 칸 밀기 → [1, 4, 4, 5, 6, 2]
- j = 0 → arr[0] = 1 > 3? No → 반복문 종료
- arr[j+1] = arr[1]에 3 삽입 → [1, 3, 4, 5, 6, 2]
➡️ 3이 4와 5 사이에 잘 들어감
- 4회전 (i = 4) 👉 바깥 반복문
- 바깥 반복문 i = 4 → insertingData = 6
- j = 3 → arr[3] = 5 > 6? No → 반복문 종료
- arr[j+1] = arr[4]에 6 삽입 (자리 그대로) → [1, 3, 4, 5, 6, 2]
➡️ 6은 이미 제자리에 있음 (변경 없음)
- 5회전 (i = 5) 👉 바깥 반복문
- 바깥 반복문 i = 5 → insertingData = 2
- j = 4 → arr[4] = 6 > 2 → 오른쪽으로 한 칸 밀기 → [1, 3, 4, 5, 6, 6]
- j = 3 → arr[3] = 5 > 2 → 오른쪽으로 한 칸 밀기 → [1, 3, 4, 5, 5, 6]
- j = 2 → arr[2] = 4 > 2 → 오른쪽으로 한 칸 밀기 → [1, 3, 4, 4, 5, 6]
- j = 1 → arr[1] = 3 > 2 → 오른쪽으로 한 칸 밀기 → [1, 3, 3, 4, 5, 6]
- j = 0 → arr[0] = 1 > 2 → No → 반복문 종료
- arr[j+1] = arr[1]에 2 삽입 → [1, 2, 3, 4, 5, 6]
➡️ 2가 3과 1 사이에 들어감