Insert Sort

1. 삽입 정렬 이란?

삽입 정렬은 실제 알고리즘에 많이 쓰이는 정렬 중 하나입니다. 퀵 정렬의 정의는 다음과 같습니다.

Insertion sort is a simple sorting algorithm that builds the final [sorted array] (https://en.wikipedia.org/wiki/Sorted_array) (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. -wiki-

삽입 정렬(insertion sort)은 최종 정렬된 배열(또는 목록)을 한 번에 하나씩 비교하여 작성하는 간단한 정렬 알고리즘이다. 이것은 빠른 정렬, 힙 정렬 또는 병합 정렬과 같은 더 진보된 알고리즘보다 큰 목록에서 훨씬 덜 효율적이다.

삽입 정렬은 두 원소 중 마지막 원소를 임시 변수에 저장한 후, 두 원소를 비교해서 값이 큰 경우에 서로 교환을 합니다.

2. 삽입 정렬 의사 코드

배열의 왼쪽부터 오른쪽 방향으로 확인하면서 최솟값을 결정합니다.
한 차례씩 이동하면서 가장 작은 값을 저장합니다.
변수에 들어 있는 값보다 작은 값이 들어 있으면 변수가 새 인덱스로 값이 대체됩니다.
최솟값이 어느 인덱스에 있는지 알고 있으면 그 인덱스 값과 패스스루를 통해 값을 교환합니다.
이 과정을 계속 반복합니다.

3. 삽입 정렬 구현

function insertSort(arr) {
    for(var i = 1; i < arr.length; i++) { // 인덱스 1부터 전체 배열을 순회한다.
        let currentValue = arr[i]; // 제거 중인 값을 currentValue 변수에 저장한다.
        let position = i - 1; // position 변수에 생성해 currentValue 왼쪽 인덱스부터 시작한다.

        while(position >= 0) { // position이 0보다 크거나 같은 동안 실행한다.
            if (arr[position] > currentValue) { // position에 있는 값이 currentValue 값보다 큰지 확인한다.
                arr[position + 1] = arr[position]; // arr[position]가 크다면 오른쪽으로 이동한다.
                position = position - 1;
            } else {
                break; // position에 있는 값이 currentValue보다 같거나 작으면 공백을 삽입할 때이니 패스스루를 끝낸다.
            }
        }
        arr[position + 1] = currentValue; // currentValue를 공백에 삽입한다.
    }
    return arr;
}