해당 포스팅에서는 정렬 기법 중 하나인 삽입정렬에 대해 설명한 후 삽입정렬을 자바스크립트로 구현해보고자 합니다.
삽입정렬은 배열을 정렬된 부분(앞 부분)과 정렬 안 된 부분(뒷 부분)으로 나누고, 정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입
하는 과정을 반복하는 정렬기법이다.
배열 nums 40 10 50 90 20
을 예시로 삽입정렬의 로직을 살펴보겠다.
배열 nums는 원소 40만 정렬되어있고 원소 10 이후로는 정렬 안 되어있다.
즉 정렬된 부분은 40, 정렬 안 된 부분은 10 50 90 20이다.
정렬 안 된 부분의 가장 왼족 원소인 10을 정렬된 부분의 알맞은 위치에 삽입해보자.
10은 40보다 앞이기에 40 앞에 삽입되어야 한다. 삽입정렬은 아래의 로직으로 삽입을 구현한다.
이러한 과정을 반복하면 오름차순 정렬된다.
input: 크기가 n인 array nums
output: 정렬된 array nums
// i = 정렬 안 된 부분의 가장 왼쪽 원소의 index
// j = i랑 값을 비교할 정렬된 부분의 원소의 index
function solution(nums) {
for (let i=1; i<n; i++) {
let x = nums[i];
let j = i-1;
while (j>=0 && nums[j] > x) {
nums[j+1] = nums[j];
j -= 1;
}
nums[j+1] = x;
}
return nums;
}
예시) 배열 A 5 25 20 10 30