개발 공부/알고리즘

[정렬 알고리즘] #3. 삽입 정렬 (Insertion Sort)

짹뚜 2022. 2. 14. 16:37

삽입 정렬

삽입 정렬은 요소를 앞에서부터 순서대로 이미 정렬된 배열과 비교를 해서 자신의 위치를 찾아서 삽입하는 알고리즘이다. 삽입 정렬은 필요할 때만 삽입을 진행하기 때문에 만약 데이터가 거의 정렬이 된 상태라면 다른 알고리즘보다 빠르게 정렬을 할 수 있다. 그러나 평균적으로 삽입 정렬의 시간 복잡도는 O(n²)이다.

알고리즘

오름차순으로 정렬을 할 때는 다음과 같이 진행한다.

 

  1. 두 번째 요소부터 반복문을 진행한다.
  2. 현재 확인할 요소의 앞부분은 이미 정렬이 된 상태이다.
  3. 앞부분의 마지막 요소부터 비교를 시작한다.
  4. 삽입할 요소보다 큰 요소들을 찾는다.
  5. 큰 값을 가진 요소들의 위치를 한 칸 뒤로 옮긴다.
  6. 지정한 위치에 삽입할 요소를 넣는다.
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(" "));
    }
}