[Algorithm]Sort-insertionSort

insertionSort Algorithm

insertionSort()은 배열을 반복하고 정렬되지 않은 각 요소를 정렬된 하위 배열의 왼쪽에 있는 올바른 위치에 삽입하여 작동합니다.

1. 배열의 첫 번째 요소는 정렬된 하위 배열로 간주된다.
2. 배열의 각 후속 요소에 대해:
   a. 요소를 정렬된 하위 배열의 요소와 비교합니다.
   b. 요소가 작을 경우 정렬된 하위 배열의 큰 요소를 오른쪽으로 한 위치 이동합니다.
   c. 정렬된 하위 배열에서 요소를 올바른 위치에 삽입합니다.
3. 배열의 모든 요소가 정렬될 때까지 반복합니다.

코드는 아래와 같습니다.

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let current = array[i];
    let j = i - 1;
    while (j >= 0 && array[j] > current) {
      array[j + 1] = array[j];
      j--;
    }
    array[j + 1] = current;
  }
  return array;
}

insertionSort() 함수는 배열을 매개 변수로 사용하고 InsertionSort 알고리즘을 사용하여 배열을 정렬합니다. 함수는 먼저 두 번째 요소(예: 인덱스 1)부터 배열을 반복하고 현재 요소를 현재 변수에 할당합니다.

결과는 아래와 같습니다.

insertionSort([4,3,2,10,12,1,5,6])
console.log(insertionSort([4,3,2,10,12,1,5,6]))//[ 1, 2, 3, 4, 5, 6, 10, 12 ]

다음으로, 함수는 현재 요소를 왼쪽에 있는 정렬된 하위 배열의 요소와 비교합니다. 현재 요소가 더 작은 경우 정렬된 하위 배열에서 더 큰 요소를 오른쪽으로 한 위치 이동합니다.

함수가 현재 요소에 대한 올바른 위치를 찾으면 정렬된 하위 배열에 요소를 삽입합니다.

함수는 배열의 모든 요소에 대해 이 프로세스를 반복하여 정렬된 배열을 만듭니다.

---

삽입 정렬은 소규모 데이터 세트를 위한 간단하고 효율적인 알고리즘입니다. 시간 복잡도가 O(n^2)이므로 대규모 데이터 세트의 경우 효율성이 떨어진다. 그러나 특히 데이터 세트가 상대적으로 작을 때는 여전히 많은 응용 분야에서 널리 사용된다.