Insertion Sort에 대해 설명해보세요.

---

Insertion Sort의 작동 방식

• Insertion Sort는 매 차례마다 해당 원소를 삽입할 수 있는 위치를 찾아 넣는 정렬 알고리즘이다.

• 두 번째 원소부터 앞에 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 원소들을 뒤로 옮기고 해당 위치에 삽입한다.

---

Insertion Sort의 특징

• 시간 복잡도
  : 최선의 경우(이미 정렬되어 있는 상태) 이동 없이 한 번의 비교만 이루어지므로 O(N)의 시간 복잡도를 가진다. 하지만 평균과 최악의 경우 O(N^2)의 시간 복잡도를 가진다.

• 공간 복잡도
  : 배열 안에서 교환을 통해 정렬이 진행되므로 추가 메모리 공간 사용 없이 O(N)의 시간 복잡도를 가진다.

• 장점

  • 구현이 간단하여 단순성이 높다.
  • 이미 정렬되어 있는 상태일 경우 매우 효울적이다.
  • 같은 O(N^2)의 시간 복잡도를 가지는 다른 정렬 알고리즘들에 비해 교환 연산이 적어 상대적으로 빠르다.

• 단점

  • 배열이 길어질수록 비효율적이다.

---

결론

Insertion Sort는 두 번째 원소부터 차례대로 앞부분의 정렬되어 있는 배열에 해당하는 위치에 삽입하여 정렬하는 알고리즘입니다. 배열이 이미 정렬되어 있는 최선의 경우에는 O(N)의 시간 복잡도를 갖지만 평균과 최악의 경우 O(N^2)의 시간 복잡도를 가집니다. 공간 복잡도는 추가 메모리 공간 사용 없이 O(N)의 공간 복잡도를 가집니다. 다른 O(N^2)의 시간복잡도를 가지는 정렬 알고리즘에 비해 상대적으로 빠르고 이미 정렬되어 있을 경우 매우 효율적이지만 배열이 길어질수록 비효율적입니다. 데이터가 적고 앞부분에 정렬되어 있는 데이터가 많을 때 사용하기 유리한 알고리즘입니다.