삽입 정렬(Insertion Sort) 란?

삽입 정렬이란?

정렬이 되어 있지 않은 '부분'의 데이터를 뽑아 정렬된 '부분'의 적절한 위치에 삽입하는 방법이다.

다시 설명하자면,

자료 배열의 모든 요스를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치에 삽입하는 정렬이다.

 

삽입정렬 장단점은?

이미 정렬이 되어있는 배열이 주어지면 자리 바꿈이 일어나지 않고, 딱 한 번씩 앞의 숫자와 비교 검사를 하기 때문에 이러한 Best 상황에서는 O(n)의 시간복잡도를 가진다.

 거의 정렬이 되어있는 배열이라면 버블, 선택, 삽입 중에선 삽입 정렬이 가장 중요하다.

하지만, 역순으로 되어있는 배열이나, 배열의 수, 즉 길이가 길다면 그만큼 비교와 자리 바꿈 횟수가 많아지므로 삽입 정렬을 사용하기엔 부적합하다.

 

시간복잡도는 ?

- 데이터가 이미 정렬된 케이스 : O(n)

: 버블 정렬, 선택 정렬과 다르게 삽입 정렬은 'break;' 키워드가 존재한다.

이미 정렬된 상태라면 정렬하려는 원소의 바로 앞 원소와 비교 시, break; 키워드를 통해 즉시 for 문을 탈출한다.

따라서, 시간 복잡도는 for 문에 의해서 결정이 됨으로 O(N)이 된다.

 

- 데이터가 역숙으로 정렬된 케이스 : O(n²) 

: 역순으로 저장되어 있는 데이터를 정렬하려면, 매 사이클마다 첫 번째 배열의 앞까지 데이터를 위치를 변경해야한다.

매 사이클마다 인덱스 0 원소에 접근하므로 N(N-1)/2. 즉 O(n²) 시간 복잡도가 된다.

 

https://www.w3resource.com/csharp-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-6.php