삽입 정렬

삽입 정렬이란?

• 순차적으로 값을 읽어서 현재 값 이전에 위치한 정렬되어 있는 값들의 적절한 곳으로 삽입하는 정렬이다.
• 현재 값 이전에 위치한 값들은 이미 정렬되어 있으므로, 현재 값이 직전 값보다 크다면 삽입이 일어나지 않는다.
• 성능
• O(n²)
• 정렬되어 있을 수록 성능이 좋다.
• 이미 정렬 되어 있을 경우(최선의 경우) 비교 횟수 : N - 1
• 역순일 경우(최악의 경우) 비교 횟수 : N(N – 1)/2

자세한 내용은 여기로