정렬 알고리즘 - 삽입 정렬의 이해와 효율적 구현 방법

삽입 정렬 개요

• 배열의 두 번째 요소부터 시작하여 그 앞의 요소들과 비교하면서 올바른 위치를 찾아 삽입하는 방식으로 작동합니다.
• 각 단계에서 정렬되지 않은 부분 중에서 하나를 선택하여 이미 정렬된 부분에 삽입합니다.

삽입 정렬 동작 원리

1. 배열의 두 번째 요소를 가져옵니다.
2. 두 번째 요소를 첫 번째 요소와 비교하여, 정렬 조건이 맞으면 삽입합니다.
3. 세 번재 요소를 앞의 정렬된 부분의 위치에 삽입합니다.
4. 과정을 반복합니다.

삽입 정렬 코드 예시

function test(arr) {
 for(let i = 1; i < arr.length; i++) {
  const cValue = arr[i]
  let j = i - 1
  while(j >= 0 && arr[j] > cValue) {
   arr[j + 1] = arr[j]
   j--
  }
  arr[j + 1] = cValue
 }
}

const arr = [5,4,3,2,1]
test(arr)

• 결과는 1,2,3,4,5로 나옵니다. 반대의 결과를 만들기 위해서는 while문 안에 arr[j] < cValue로 바꿔야합니다.

삽입 정렬 시간 복잡도

• 정렬이 다 된 경우에는 while문이 생략되기 때문에 O(n)에 대한 시간 복잡도를 가집니다.
• 최악이나 평균의 경우 O(n^2) 시간 복잡도를 가집니다.

삽입 정렬 장점

• 구현이 간단합니다.
• 작은 크기의 배열이나 거의 정렬된 배열에서 효율적입니다.
• 메모리 사용량이 작습니다. 추가적인 메모리 할당이 필요하지 않습니다.

삽입 정렬 단점

• 배열의 크기가 클수록 비효율적입니다.

삽입 정렬 활용

• 보조 정렬 알고리즘으로 사용됩니다.
• 데이터가 실시간으로 입력될 때, 새로운 데이터를 기존의 정렬된 배열에 삽입하는 경우에 유용합니다.