삽입정렬?
삽입 정렬(insertion sort)은 한 번에 한 원소씩 정렬된 배열을 만들어가는 알고리즘이다. 첫 번째 원소는 정렬이 끝났다고 가정하고, 두 번째 원소와 비교해 첫 번째 원소보다 더 작다면 첫 번째 원소 앞으로 옮긴다. 그래서 처음 두 원소의 정렬이 끝나면 다음엔 세 번째 원소와의 비교를 계속한다.(첫 번째, 두 번째, 세 번째 위치 중 어디에 삽입할지 결정한다.)
이 링크를 통해 삽입 정렬이 어떻게 작동하는지 참고할 수 있다.
시간복잡도
시간 복잡도가 O(n^2) 이지만, 원소(element)의 수가 작은 배열이라면 삽입 정렬은 선택 정렬, 버블 정렬 보다 성능이 우수하다.
선택정렬 구현
const insertionSort = arr => {
const length = arr.length;
let j, temp;
for (let i=1; i<length; i++){
j = i;
temp = arr[i];
while (j>0 && arr[j-1] > temp){
arr[j] = arr[j-1];
j--;
}
arr[j] = temp
}
return arr;
}- 알고리즘에서 사용할 변수 3개(length, j, jump) 를 선언한다
- 첫 번째 원소는 이미 정렬된 상태라고 가정하고 2번째, 즉 인덱스 1의 원소부터 배열을 순회하는 것에 주의하라
- 보조 변수(auxiliary variable) j 에 i 를, 인덱스 i의 원소를 temp에 담아두고, 나중에 제자리를 찾아 집어넣을 것이다.
- 이제 이 원소의 제자리를 찾아야 한다. j가 0보다 크고(배열 인덱스는 0 부터 시작하므로 음의 값을 갖지 않는다) 직전 인덱스의 원소가 인덱스의 i 의 원소보다 크면, 직전 인덱스 원소를 i 로 옮기고 j를 1만큼 감소시킨다.
- 이러한 과정을 반복 후 마지막에 제자리를 찾아 원소를 삽입한다.
배열 [3, 5 ,1 ,4, 2] 를 삽입 정렬 알고리즘을 사용해 [1, 2, 3, 4, 5]로 정렬하는 과정을 살펴보자
- 3은 정렬된 상태이므로 두 번째 원소 5부터 비교 한다. 3 < 5 이므로 5는 위치 변동 없이 그 자리에 남게 된다. 이것으로 3, 5 까지 정렬이 끝났다.
- 그 다음 정렬할 원소는 세 번째 위치한 1이다. 5 > 1 이므로 5는 1과 위치를 바꾸고 3 > 1 이므로 3 역시 두 번째 위치로 옮긴다. 그리고 1을 첫 번째 위치에 두어야 할지 결정해야 한다. 배열 원소의 인덱스는 0 부터 시작하고 음의 값은 갖지 않으므로 1은 첫 번째 위치에 삽입한다. 여기까지 1, 3, 5의 정렬이 끝났다.
- 다음은 4 이다. 4는 현재 위치(인덱스3)에 그대로 남게 될지, 아니면 앞으로 당겨야 할지 확인해보자. 5 > 4 이므로 5는 인덱스 3으로 옮겨지고, 3 < 4 이므로 4는 인덱스 3에 삽입된다.
- 이제 원소 2가 남았다. (인덱스 4) 5 >2 이므로 5는 인덱스 4로 옮겨진다. 4 > 2 이므로 4 역시 인덱스 3으로 옮겨야 한다. 3 도 3 > 2 이므로 자리를 옮긴다. 1 < 2 이므로 2는 두 번째 자리에 위치시킨다.
- 이렇게 정렬이 마무리 된다.