[정렬 알고리즘] - 삽입 정렬 O(n²)

삽입 정렬

이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식으로

O(n²)의 시간복잡도로 느린편이나 구현하기는 쉽다.

 

핵심 이론

선택된 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입한다.

 

 

Do it! 알고리즘 코딩테스트 핵심 이론 유투브 강의에서 발췌

 

(첫번째 인덱스 선택된 데이터의 경우 정렬된 데이터 범위 그 자체 이므로 정렬할수가 없다.
따라서 LOOP는 돌지만 마치 정렬되지 않은것처럼 다음 LOOP로 넘어간다.)

최 우측의 5번째 데이터 삽입 시 선택된 데이터40은 인덱스 1번의 32보다 크다.

이때 앞의 데이터들은 모두 정렬된 데이터들 이므로 선택한 데이터 40은 인덱스 1번의 32보다 작지 않은 조건에 의해
더이상 앞의 데이터까지 비교연산을 수행하지 않는다.

 

삽입정렬 수행 과정

1. 현재 index에 있는 데이터 값을선택
2. 현재 선택한 데이터가 정렬된 데이터 범위에서 삽입될 위치를 탐색 (크기 비교)
3. 삽입 될 위치부터 현재 정렬할 대상 index 위치까지 shift연산을 수행한다.
4. 삽입 될 위치에 현재 선택한 데이터 삽입 후 정렬 대상 index를 ++ 1 증가시킨다.
5. 전체 데이터 크기만큼 index가 증가할 때 까지, 즉 데이터가 없을 때 까지 반복한다.

 

데이터가 많을 경우 적절한 삽입 위치를 탐색하는 부분에서 이진탐색(Binary Search) 등과 같은 탐색 알고리즘 사용으로 시간 복잡도를 감소시킬 수 있다.