삽입 정렬 ( insertion sort )

삽입 정렬 ( Insertion sort )

삽입 정렬이란?

삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

시간 복잡도는 O(n^2)지만, 인풋이 적고, 모든 데이터가 들어와 있다면 선택 정렬, 거품 정렬과 같은 O(n^2) 알고리즘에 비교하여 빠르다.

코드와 설명

const InsertionSort = arr => {
  let temp, j;
  for ( let i = 1; i < arr.length; i++ ) {
    temp = arr[i];
    j = i;
    while( j > 0 && arr[j-1] > temp ) {
      arr[j] = arr[j-1];
      j--;
    }
    arr[j] = temp;
  }
  return arr;
}

console.log(InsertionSort([5,1,6,3,2,4,8]))

구현한 코드 설명하는게 코드짜는거보다 더어려운것 같다.

1. 배열의 i번째 인덱스 값을 temp에 담는다.
2. i 보다 작은 인덱스 j에 대해 각각 비교를 하며 temp가 값이 더 클때까지 j를 줄이며 반복문을 돌리며, 참일 경우에 한칸씩 뒤로 밀어준다.
3. while문에서 나오면 나온 지점에 temp를 넣어준다.
4. for문 나오면 리턴

코드 비주얼라이저로 직접 과정을 보면 이해가 쏙쏙!