삽입 정렬 알고리즘 (Insertion Sort Algorithm)

 

삽입 정렬(Insertion Sort)은 간단한 정렬 알고리즘 중 하나로, 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 요소를 정렬된 부분에 적절한 위치에 삽입하는 방식으로 동작합니다.

그림 1

아래는 JavaScript로 구현된 삽입 정렬 알고리즘의 예시입니다

function insertionSort(arr) {
  const n = arr.length;

  for (let i = 1; i < n; i++) {
    let current = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }

    arr[j + 1] = current;
  }

  return arr;
}

// 사용 예시
const array = [8, 4, 2, 6, 10];
const sortedArray = insertionSort(array);
console.log(sortedArray); // [2, 4, 6, 8, 10]

위의 코드에서 insertionSort 함수는 삽입 정렬을 수행하는 함수입니다. 주어진 배열을 반복하면서 각 요소를 정렬된 부분에 삽입합니다. current 변수에 현재 요소를 저장하고, j 변수를 이용하여 현재 요소를 삽입할 위치를 찾습니다. 정렬된 부분의 요소와 비교하며 적절한 위치를 찾으면 요소를 한 칸씩 오른쪽으로 이동시키고, 최종적으로 current를 삽입합니다.

위의 예시 코드를 실행하면 정렬된 배열이 출력됩니다. 이와 같은 방식으로 삽입 정렬은 요소를 하나씩 삽입하면서 배열을 정렬하는 효율적인 알고리즘입니다. 그러나 배열의 크기가 큰 경우에는 다른 정렬 알고리즘보다 더 많은 비교와 교환 연산을 필요로 할 수 있으므로, 큰 데이터셋에 대해선 다른 알고리즘을 고려하는 것이 좋습니다.