개발 공부/알고리즘
[정렬 알고리즘] #3. 삽입 정렬 (Insertion Sort)
짹뚜
2022. 2. 14. 16:37
삽입 정렬
삽입 정렬은 요소를 앞에서부터 순서대로 이미 정렬된 배열과 비교를 해서 자신의 위치를 찾아서 삽입하는 알고리즘이다. 삽입 정렬은 필요할 때만 삽입을 진행하기 때문에 만약 데이터가 거의 정렬이 된 상태라면 다른 알고리즘보다 빠르게 정렬을 할 수 있다. 그러나 평균적으로 삽입 정렬의 시간 복잡도는 O(n²)이다.
알고리즘
오름차순으로 정렬을 할 때는 다음과 같이 진행한다.
- 두 번째 요소부터 반복문을 진행한다.
- 현재 확인할 요소의 앞부분은 이미 정렬이 된 상태이다.
- 앞부분의 마지막 요소부터 비교를 시작한다.
- 삽입할 요소보다 큰 요소들을 찾는다.
- 큰 값을 가진 요소들의 위치를 한 칸 뒤로 옮긴다.
- 지정한 위치에 삽입할 요소를 넣는다.
function insertionSort(arr) {
for(let i = 1; i < arr.length; i++){
let currentIndex = i;
for(let j = i - 1; j >= 0; j--){
if(arr[currentIndex] < arr[j]){
// 만약 삽입할 요소가 작다면 swap을 해줌으로써 큰 값을 뒤로 한 칸 옮긴다
const temp = arr[currentIndex];
arr[currentIndex] = arr[j];
arr[j] = temp;
currentIndex = j;
} else {
break;
}
}
console.log(arr.join(" "));
}
}