삽입 정렬 ( 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문 나오면 리턴

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


  1. BlogIcon hanjung 2017.11.09 17:06 신고

    '시간 복잡도는 O(n^2)지만, 인풋이 적고, 모든 데이터가 들어와 있다면 선택 정렬, 거품 정렬과 같은 O(n^2) 알고리즘에 비교하여 빠르다' 라고 되어있는데 궁금한점이 있습니다.
    1. 그러면 데이터가 적을 때 머지나 퀵정렬보다는 안빠른지?
    2. 항상 셀렉션, 버블보다 빠른지? 아니라면?
    3. 최악으로 시간이 오래발생하는 조건이 어떤건지

    • BlogIcon takeu takeU 2017.11.09 17:14 신고

      집가서답변해드리죠(몰라서시간버는거아님)

    • BlogIcon takeu takeU 2017.11.09 19:17 신고

      1. 데이터가 적다는 가정 하에 속도의 차이는 많이 나지 않는걸로 알고있습니다. 코드가 간단해 사용하기 쉬운 이유로, 그나~마 사용을 한다 정도로 설명할 수 있을 것 같습니다.

      2. 항상이란 단어는 사용할 수 없겠지만, 일반적으로는 삽입정렬이 셋중에는 성능이 가장 좋다 알려져있습니다. 각 정렬방법에 대한 코드를 어떻게 짜느냐에 따라, 데이터의 현재 정렬 상태에 따라 속도는 달라질 수 있습니다.

      3. 데이터가 역순으로 정렬되어 있을 때 가장 시간이 오래 걸립니다.

      틀린점이나 부족한 설명이 있다면 지적 및 추가 부탁드립니다 ^~^

  2. BlogIcon hanjung 2017.11.10 17:25 신고

    1. 본인이 사용하는 언어나 C++에서 기본으로 제공하는 sort 메서드의 내부구조가 어떻게 구현되었는지 한번 보는 것을 ㅊㅊ

+ Recent posts