삽입 정렬(Insertion Sort)의 특징

• 비교 기반 알고리즘
• 안정적 정렬
• 제자리 정렬
• 최악 O(n^2), 최적 O(n)의 수행시간
• 이미 정렬된 배열에 대해서 최적의 수행시간을 보이며, 역순으로 정렬된 배열에 대해서 최악의 수행시간을 보인다.

알고리즘

1. 리스트는 정렬이 된 부분(어두운 색)과 정렬이 아직 안 된 부분(밝은 색)으로 나누어진다.
2. 0번 인덱스는 정렬이 된 것으로 간주한다.
3. 정렬이 아직 되지 않은 부분의 첫 번째 데이터를 이미 정렬이 된 데이터들과 대소를 비교하여 맞는 자리에 삽입한다. (그림의 1, 2 행에서 정렬이 아직 되지 않은 데이터의 첫번째 원소 26을 정렬이 된 부분 54 앞에 삽입하는 것을 볼 수 있다)
4. 다시 정렬이 되지 않은 부분의 첫번 째 원소 93을 정렬이 된 부분에서 54 뒤에 삽입한다.
5. 위의 과정을 반복하여 정렬을 완료한다.

구현

class InsertionSort {
    constructor(_list) {
        const list = _list;

        const insertionSort = list => {
            if (Array.isArray(list)) {
                if (list.length === 0) {
                    return [];
                }

                for (let i = 1; i < list.length; i++) {
                    for (let j = 0; j < i; j++) {
                        if (list[i] < list[j]) {
                            const temp = list[j];
                            list[j] = list[i];
                            list[i] = temp;
                        }
                    }
                }

                return list;
            }
        };
        return insertionSort(list);
    }
}

//------------------------------------

const data = [18, 15, 23, 28, 52, 59, 13];

const sortedData = new SelectionSort(data);

console.log(sortedData); // [13, 15, 18, 23, 28, 52, 59]