InsertionSort 정리

목표

• InsertionSort 알고리즘 이해
• InsertionSort 알고리즘을 자바스크립트로 구현
• InsertionSort 특징 이해
• InsertionSort 시간복잡도 이해

 

 

InsertionSort 알고리즘 개념

• 삽입 정렬은 두번째 자료부터 시작하여 그 앞의 자료들과 비교하며 삽입할 위치를 정한다. 나머지 자료들은 뒤로 밀어낸다.

 

 

InsertionSort 예시

https://www.geeksforgeeks.org/recursive-insertion-sort/

InsertionSort 자바스크립트 코드

const insertionSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  // 두번째 자료부터 시작하여 그 앞의 모든 자료들과 비교하여 삽입할 위치를 정한다.
  // 삽입할 위치가 정해지면 그 위치 뒤쪽의 자료들은 뒤로 밀려난다.
  // 새로운 배열을 만들고 정렬되있는 인덱스까지 차례대로 할당한다.
  // 정렬되어있지 않다면 새로운 배열안의 요소들과 차례대로 비교한다.
  // 큰 값을 만나면 그 앞자리에 삽입한다.

  //새로운 배열을 만든다.
  let list = [arr[0]]

  for(let i = 1;i<arr.length;i++){
    //list는 이미 정렬되어 있는 배열이므로 list에서 가장 큰 마지막 요소랑만 비교한다.
    //list[list.length-1]보다 arr[i]이 크다면 list의 가장 뒤에 arr[i]를 push하면 된다.
    if(arr[i]>list[i-1]) list.push(arr[i])

    //list[list.length-1]보다 arr[i]이 작다면 list의 값들과 arr[i]를 비교한다.
    else{
      for(let j = 0;j<list.length;j++){
      //arr[i]보다 큰 list[j]를 만나면
        if(list[j]>arr[i]){
        //그 앞에 arr[i]를 끼워 넣는다.
          list = [...list.slice(0,j),arr[i],...list.slice(j)]
          //그리고 반복문 종료
          break;
        }
      }
    }

  }return list
};

 

InsertionSort 알고리즘의 특징

• 장점
  • 안정적이다.
  • 알고리즘 자체가 간단하기 때문에 레코드 수가 적을경우 다른 복잡한 정렬방법보다 유리할 수 있다.
  • 대부분의 레코드가 정렬되어 있는 배열에서 효율적이다.

 

• 단점
  • 비교적 많은 레코드들의 이동이 있다.
  • 레코드 수가 많고 레코드 크기가 클 경우 적합하지 않다.

 

InsertionSort 시간복잡도

• 최선의 경우 : 이동없이 1차 반복문에서 1번의 비교씩만 n번 이루어진다 -> O(n)

 

• 최악의 경우(역정렬되어있을 경우) :
  • 1차 반복문에서의 비교 n번 * 2차반복문에서 j번(break만나기 전까지)만큼의 비교 수행
  • 각 단계에서 n번의 이동 발생 -> O(n^2)

 

정렬 알고리즘 시간복잡도 비교

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

• 단순, 비효율 : 삽입정렬, 선택정렬, 버블정렬
• 복잡, 효율 : 퀵정렬, 힙정렬, 합병정렬, 기수정렬