[알고리즘 | JS] sorting

끼워 넣다 정렬 기준

삽입 정렬은 버블 정렬 및 선택 정렬과 매우 유사합니다. 기본 정렬 알고리즘은 이 세 가지를 결합합니다.

몇 가지 주요 차이점이 있으며 실제로 삽입 정렬에는 몇 가지 장점이 있습니다.

• 삽입 정렬이 잘 되는 상황이 있는 것 같다 -> 거의 정렬된 데이터에 새로운 데이터가 들어올 때
• 상황의 예: 라이브 및 스트리밍을 통해 들어오는 데이터를 즉시 입력해야 하는 상황, 데이터가 들어오고 지속적으로 재정렬되고 지속적인 정렬을 통해 최신 상태로 유지되어야 하는 상황

2. 삽입 정렬 작동 방식

이 정렬은 배열의 대부분을 점진적으로 차지하여 정렬을 구축하며 항상 가장 많은 것이 정렬됩니다.

그러므로 개별적으로 이동하는 대신 한 번에 가장 큰 항목 또는 가장 작은 항목을 찾습니다. 각 요소를 가져와 정렬된 절반의 적절한 위치에 배치합니다.

• 그림을 보면 한 번에 하나의 요소를 올바른 위치에 삽입하면서 배열의 정렬된 부분을 점진적으로 구축하고 있음을 알 수 있습니다.
• 한 번에 하나의 요소를 가져와 올바른 위치에 삽입하기 때문에 삽입 정렬이라고 합니다.
• 참고: 배열의 첫 번째 요소는 정렬된 부분으로 간주됩니다.

insertSort.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)는 최악의 경우를 기준으로 시간복잡도를 고려하므로 삽입정렬의 시간복잡도는 O(n^2)이다.

---

기본 정렬 알고리즘 요약

• 버블 정렬 및 삽입 정렬은 데이터가 대부분 정렬되지만 선택 정렬은 그렇지 않은 경우 좋은 선택입니다.
• 선택 정렬의 장점은 이해하기 쉽다는 것입니다.
• 삽입 정렬의 특별한 점은 데이터를 추가로 정렬해야 할 때 잘 작동한다는 것입니다. 새 항목을 추가하는 것은 모든 데이터가 준비된 일종의 일회성 프로세스입니다.
• 위의 세 가지 정렬 알고리즘은 매우 작은 데이터 세트에 적합합니다. -> 작은 데이터 세트에 효과적입니다.