오늘은 정렬 알고리즘 중 단순하게 비교 기반 전략을 활용한 정렬 알고리즘인 삽입 정렬에 대해 소개하려고 한다
참고로 삽입 정렬은 이름에서 알 수 있듯이 원소를 적절한 위치에 삽입하여 정렬을 진행하는 방식이다
삽입 정렬이란?
삽입 정렬은 배열의 각 원소를 알맞은 위치에 삽입하는 방식으로 정렬하는 알고리즘으로
앞쪽부터 시작해서 앞쪽의 배열은 정렬된 상태로 유지되며 해당 위치의 원소부터 그 이전의 원소들과 비교하여 자신의 위치를 찾아가는 방식의 알고리즘이다
삽입 정렬의 작동 방식
글로만 보면 잘 이해가 안될 수 있으니 예시를 들어 설명하자 오름차순으로 삽입 정렬 알고리즘을 사용한다고 했을 때
정렬해야 하는 리스트: [9, 7, 5, 11, 12, 2] 첫 번째 원소 9는 이미 정렬된 상태로 간주되기에 7부터 시작한다
첫 번째 진행:
1
2
3
[9, 7, 5, 11, 12, 2] -> [7, 9, 5, 11, 12, 2]
두 번째 원소 7은 9보다 작으므로 7을 9의 앞으로 이동시킨다
두 번째 진행:
1
2
3
[7, 9, 5, 11, 12, 2] -> [5, 7, 9, 11, 12, 2]
세 번째 원소 5는 9보다 작고 7보다도 작으므로 5를 7의 앞으로 이동시킨다
세 번째 진행:
1
2
3
4
[5, 7, 9, 11, 12, 2] -> [5, 7, 9, 11, 12, 2]
네 번째 원소 11은 9보다 크므로 그대로 둔다
이와 같은 과정을 반복하면 리스트에 전체 원소가 오름차순으로 정렬된다
삽입 정렬의 장단점
마지막으로 삽입 정렬 알고리즘에 장단점을 알아보자
장점:
- 작은 양의 데이터에 대해서는 빠른 실행 시간을 보인다
- 추가 메모리를 거의 사용하지 않는다 (인플레이스 정렬)
- 대부분 정렬되어 있는 데이터에 대해서는 매우 효율적이다
단점:
- 최악의 경우 시간 복잡도가 O(n2)이다
- 데이터의 양이 많을 경우 다른 알고리즘에 비해 비효율적이다