[알고리즘] 삽입 정렬 (Insertion Sort)

[알고리즘] 삽입 정렬 (Insertion Sort)

Tags

Algorithm

삽입 정렬 (Insertion Sort)

개념

이름 그대로 배열을 정렬할 때 적절한 위치에 삽입하는 방식의 정렬 알고리즘이다.

시간 복잡도는 배열의 상태에 따라 O(n) ~ O(n²) 이 나온다.

원리

첫 번째 원소를 이미 정렬된 걸로 간주한다.

두 번째 원소를 첫 번째 원소와 비교해 적절한 위치로 자리를 이동시킨다.

세 번째 원소를 앞의 두 원소와 비교해 적절한 위치로 자리를 이동시킨다.

모든 원소가 처리 될 때 까지 반복한다.

예시


[8, 3, 5, 4, 6]
[3, 8, 5, 4, 6] // 8과 3을 비교
[3, 5, 8, 4, 6] // 5를 적절한 위치에 삽입
[3, 4, 5, 8, 6] // 4를 적절한 위치에 삽입
[3, 4, 5, 6, 8] // 6를 적절한 위치에 삽입

특징

정렬이 어느정도 되어 있는 배열, 특히 크기가 작은 데이터 세트를 정렬할 때 적합하다.

반대로 말하면 배열이 클 경우 시간복잡도가 커질 수 있다.