3.4Insertion Sort

Insertion Sort

Insertion Sort는 배열의 한쪽에 정렬된 부분을 만들고, 그 부분을 늘려가며 정렬하는 방식의 정렬 알고리즘이다. 원리는 아래와 같다:

1. 배열의 첫 두개 요소를 뽑는다.
2. 두 요소를 비교해서 정렬한다.
3. 다음 요소를 찾아, 앞의 정렬된 부분과 비교해 올바른 위치에 삽입한다.
4. 끝까지 반복한다.

자바스크립트로는 아래와 같이 구현할 수 있다. 아래는 배열의 오른쪽에서부터 왼쪽으로 정렬한 예시다:

javascript
function insertionSort(arr){
  for(let i = 1; i < arr.length; i++){
    let currentVal = arr[i];
    for(let j = i - 1; j >= 0 && arr[j] > currentVal; j--){
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = currentVal;
  }

  return arr;
}