[알고리즘] 2장_삽입 정렬

📌 삽입 정렬

: 좌측으로부터 한 원소씩 제 자리에 삽입하는 방법

• O(n²)

🔎
1. 배열의 두 번째 요소(5)부터 시작함
2. 현재 key 값보다 큰 값을 하나씩 탐색하며 비교함
3. 현재 key 값보다 큰 값(8)을 오른쪽으로 한칸 이동함
:
위의 단계를 반복한다.

❗ 삽입 정렬의 특징

• 최악의 경우: 키가 내림차순으로 이미 정렬되어 있는 경우
• 비교 횟수: n(n+1)/2 - 1
• 평균 비교 횟수도 O(n²)
• 안정적인 제자리 정렬