[Javascript] 정렬 - 삽입정렬(Insertion Sort)

1. 삽입 정렬

각 숫자를 적절한 위치에 삽입하는 정렬 기법

 

동작 방식

1. 각 단계에서 현재 원소가 삽입될 위치를 찾는다.

2. 적절한 위치에 도달할 떄까지 반복적으로 왼쪽으로 이동한다.

 

시간 복잡도

• 삽입 정렬이란 각 원소를 적절한 위치에 삽입하는 정렬 기법
• 매 단계에서 현재 처리중인 원소가 삽입될 위치를 찾기위해 약 N번의 연간이 필요하다.
• 결과적으로 약 N개의 단계를 거친다는 점에서 최악의 경우 O(N²)의 시간 복잡도를 가진다.

 

삽입정렬 예시

*삽입 정렬을 수행할 떄는 처음에 첫번째 원소는 정렬이 되어있다고 고려한다.

 

 

소스코드 예시

//삽입정렬함수
function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++){
        for (let j = i; j > 0; j--) {
            if(arr[j] < arr[j - 1]) {
                let temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
            else {
            	//자기보다 작을 경우 그 자리에서 멈춤
                break;
            }
        }
    }
}

let points = [40, 100, 1, 5, 25, 10];

insertionSort(points);
console.log(points); // [1,5,10,25,40,100]