[알고리즘 | JS] sorting algorithm(정렬 알고리즘)3 - insertion sort

Insertion sort (삽입 정렬)

삽입 정렬은 버블 정렬 및 선택 정렬과 꽤 비슷하다. 기초 sort 알고리즘으로 이 3가지가 묶임

몇 가지 주요 차이점이 있고, 사실상 삽입 정렬이 더 유리한 지점이 있다. 

• 삽입 정렬이 잘 작동하는 상황이 존재한다는 소리 -> 거의 정렬된 데이터에 새로운 데이터가 들어올 때 
• 상황 예시: 라이브 & 스트리밍 방식으로 들어온 데이터를 즉시 입력해야 하는 상황, 데이터가 들어와서 계속 재정렬하고 실행중인 정렬을 유지하여 최신 상태로 두어야 할 상황

2. 삽입 정렬의 동작 방식

이 정렬은 배열의 과반을 점차적으로 만들어 정렬을 구축하며, 과반은 항상 정렬되어 있다.

따라서 하나씩 이동하거나, 한 번에 가장 큰 요소를 찾거나 한 번에 가장 작은 요소를 찾는 대신 각 요소를 취하여 정렬되어 있는 절반 속 해당되는 위치에 배치한다.

Insertion Sort ref:  JavaScript 알고리즘 & 자료구조 마스터클래스 from 유데미

• 그림을 보면 한 번에 하나의 항목을 올바른 위치에 삽입해서 배열의 정렬도니 부분을 점진적으로 구축하는 것을 볼 수 있다. 
• 한 번에 하나의 요소만 취해서 올바른 위치에 삽입하기 때문에 삽입 정렬이라 하는 것이다.
• 유의점: 배열의 가장 맨 처음 요소는 정렬된 부분으로 간주한다.

insertionSort.js

function insertionSort(arr) {
    for (var i = 1; i < arr.length; i++) {
      var currentVal = arr[i];
      for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
        arr[j + 1] = arr[j];
        console.log(arr);
      }
      arr[j + 1] = currentVal;
    }
    return arr;
  }
  insertionSort([2234, 634, 2, 156, 343]);

• 한번 보고 이해가 잘 가지 않아서 i와 j의 값이 어떻게 들어오는 지 확인해보는 방식이 필요할 거 같다. 

3. 삽입 정렬의 시간 복잡도 

최적의 경우 O(n) 최악의 경우 O(n^2) 평균적으로 O(n^2)이다.

• 하지만 시간 복잡도는 최악의 경우를 기준으로 간주하기 때문에 O(n^2)가 삽입 정렬의 시간 복잡도이다.

---

Basic Sorting Algorithms 정리 

ref: JavaScript 알고리즘 & 자료구조 마스터클래스 from 유데미

• 버블 정렬과 삽입 정렬은 데이터가 거의 다 정렬되어 있는 상태라면 좋은 선택이 될 수 있지만 선택 정렬은 그렇지 못하다. 
• 선택 정렬의 장점은 이해하기 쉽다는 점이다.
• 삽입 정렬의 특별한 점은 데이터를 계속 정렬해야 할 경우 효과가 좋다는 것이다. 새 요소를 추가할 때, 모든 데이터가 준비된 일종의 일회성 작업일 때를 말한다.  
• 위의 3가지 sorting 알고리즘은 아주 작은 데이터 집합에서 잘 작동한다. -> data set이 작을 때, 효과적이다.