단순 삽입 정렬

이번에 소개할 정렬 방식은 단순 삽입 정렬입니다. 단순 삽입 정렬은 셔틀 정렬이라고 부르기도 합니다.

---

1. 단순 삽입 정렬

단순 삽입 정렬은 선택한 요소를 선택한 요소 앞쪽의 알맞은 위치에 삽입하는 정렬입니다. 단순 삽입 정렬의 시간 복잡도도 O(n^2)로 단순 선택 정렬, 버블 정렬과 같습니다.

선택 정렬과 마찬가지로 정렬된 부분과 정렬되지 않은 부분으로 나누어서 이용합니다. 자세한 삽입 정렬법은 그림으로 소개해드리겠습니다.

위와 같은 배열이 있다고 할 때 단순 삽입 정렬은 0번째가 아닌 1번째 인덱스 부터 정렬을 시작합니다. 그리고 첫번째 요소인 0번 인덱스는 정렬된 부분이라고 두고 시작합니다.

1번째 인덱스 요소인 7과 왼쪽요소를 비교합니다. 이때 왼쪽 요소는 정렬된 부분의 가장 마지막 요소입니다. 즉 정렬된 부분이 많아질수록 정렬된 부분에서 가장 큰 요소와 비교하게 되는 것이죠.

---

다음으로 정렬되지않은 부분의 첫 번째요소인 4를 정렬할 차례입니다. 바로 왼쪽 요소와 비교합니다.

비교 결과 비교한 왼쪽 요소가 현재 요소보다 크기에 두 요소의 자리를 바꿔줍니다. 그리고 한 번 더 왼쪽 요소와 비교합니다. 그림에서는 3보다 4가 크니 올바른 정렬 위치를 찾았습니다.

---

다음으로는 2를 정렬할 차례입니다. 정렬되지 않은 부분의 첫 요소인 2와 그 왼쪽 요소를 비교합니다. 2가 더 작으니 7을 밀어냅니다.

그리고 다시 2와 그 왼쪽 요소를 비교합니다.

또 한번 2와 왼쪽 요소를 비교했더니 여전히 2가 작습니다.

 

이런 방식으로 뒤에 정렬되지 않은 부분들도 비교해가며 정렬합니다.

---

이런식으로 컬렉션의 내부를 정렬하게 됩니다.

선택 정렬과 다른점은 선택 정렬은 정렬되지 않은 부분의 가장 작은 부분을 골라서 정렬했고, 삽입 정렬은 정렬되지 않은 부분의 첫 요소를 선택해서 올바른 위치로 삽입해서 정렬했다는 점입니다.

그리고 정렬과정에서 왼쪽 요소만을 비교하고 작다면 왼쪽의 요소를 한 칸씩 뒤로 밀어내어서 올바른 위치를 찾을 때 까지 반복 수행합니다.

 

 

2. 단순 삽입 정렬 구현

let simpleInsertionSort = (arr) => {
    //인덱스 1부터 정렬 시작
    for (let i = 1; i < arr.length; i++) {
        let j;
        let temp = arr[i];  //인덱스i 요소를 정렬하며 교환하기 위해 임시 저장

        //왼쪽 요소가 현재 요소(arr[j]===arr[i])보다 큰 것을 찾을 때까지 탐색
        for (j = i; (j > 0 && arr[j - 1] > temp); j--) {
            //왼쪽 요소를 현재 위치에 삽입
            arr[j] = arr[j - 1];
        }
        //교환이 모두 완료되면 현재 위치에 temp에 저장된 요소를 삽입
        arr[j] = temp;
    }

    return arr;
};

---

https://github.com/Bam-j/algorithm-study/blob/main/study-code/sort/simple-insertion-sort.js

GitHub - Bam-j/algorithm-study: 블로그 알고리즘 정리 포스트 코드 수록 + 코딩 테스트 코드 수록