Insertsort(삽입정렬)
[2023.05.19 ~ 2023.05.25] 동안 공부한 삽입정렬이다.
해당 포스트는 누구나 자료구조와 알고리즘 개정 2판을 참고하여 작성되었다.
✔ 정렬알고리즘 중 삽입정렬에 대해 정리해보자 💥
Insertsort
정렬되지 않은 배열이 주어졌을 때, 배열을 정렬시킬 수 있는 방법중 하나이다.
삽입정렬단계
값을 꺼내서 올바른 위치에 넣는다.
- 인덱스 1의 값을 삭제하고 임시 변수에 저장한다.(인덱스 1의 값은 공백)
- 인덱스 1 이전의 값을 임시 변수의 값과 비교한다. if(인덱스 1이전 값 > 임시변수){ 오른쪽 방향으로 값을 한 셀 옮긴다. }
- 2의 단계를 임시변수보다 작거나 같은 값을 만날때까지 반복한다.
- 비어있는 공백에 임시 변수의 값을 넣는다. (첫번째 패스스루 🏈)
배열의 마지막 인덱스까지 패스스루를 실행한다.
마지막 패스스루에서는 배열이 완벽히 정렬되어있다.✨
삽입정렬 만들어보기
책에 나와있는 파이썬 코드를 자바스크립트로 구현해보았다.
function solution(arr) {
for (let i = 1; i < arr.length; i++) {
let temp_value = arr[i];
let position = i - 1;
while (position >= 0) {
if (arr[position] > temp_value) {
arr[position + 1] = arr[position];
position = position - 1;
} else break;
}
arr[position + 1] = temp_value;
}
return arr;
}
let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr));
// 답: [5, 7, 11, 13, 15, 23]
삽입정렬의 효율성
삽입정렬은 삭제 -> 비교 -> 시프트 -> 삽입 총 4 단계를 거친다.
최악의 시나리오
비교는 삭제된 값보다 큰 값일 경우 수행되므로 가장 최악의 시나리오는 크기가 큰 순으로 숫자가 들어가 있는 배열이다. 최악의 시나리오일 경우, 원소 N개 일때, 비교 1 + 2 + 3 + 4 + .. + N-1, 시프트 1 + 2 + 3 + 4 + … + N-1, 삽입 N-1, 삭제 N-1 가 일어난다. 총, N^2 + 2N - 2단계로 O(N^2)의 시간복잡도가 걸린다.
이렇게 따지면 버블정렬과 선택정렬은 O(N^2) 이지만 버블정렬은 O(N^2) 인데 비해 선택정렬이 N^2/2로 조금 더 빨랐다. 삽입정렬도 N^2 이므로 선택정렬이 삽입정렬에 비해 빠르다고 할 수 있다.
평균 시나리오
평균적인 시나리오는 어느정도 임의로 데이터가 정렬된 경우이다. 이 경우 패스스루마다 모든 데이터 나 일부데이터를 비교하고 시프트하거나, 아예 비교와 시프트를 거치지 않는 단계도 있을지도 모른다. 즉, 어떤 패스스루에서는 삭제한 값의 인덱스보다 작은 인덱스들의 값을 비교할때, 삭제한 값보다 작은 값을 만나면 일찍 패스스루를 종료할 수 있기 때문이다.
따라서 삽입 정렬이 최악의 시나리오에서 N^2 단계가 걸린다면 평균 시나리오에서는 약 N^2 / 2 단계가 걸린다고 할 수 있다.
선택정렬과 삽입정렬중 어느것이 더 나을까?
평균적인 시나리오라면 두 정렬은 유사하게 수행된다. 거의 정렬된 데이터를 다룬다면 삽입정렬이 더 낫다. 역순으로 정렬된 최악의 시나리오에서는 선택정렬이 더 빠르다.
