앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 삽입하는 방식
시간 복잡도가 입력 자료의 구성에 따라 달라진다.
for i = 1 to n
정렬된 a[0]부터 a[i-1] 숫자 들과 차례대로 비교하여 a[i]보다 첫번째로 큰 수의 자리에 a[i] 값을 두고 그 자리부터 이후에 있는 값들의 인덱스를 뒤로 미뤄준다.
시간복잡도: O(n²)
장점
- 구현이 간단하다.
- 입력 자료가 정렬되어 있으면 있을 수록 빨라진다. 따라서 같은 시간복잡도를 가지는 다른 정렬(선택, 버블) 보다 효율이 높다.
- 같은 값인 경우 상대적 위치가 바뀌지 않는다. -> 안정한 정렬
- 주어진 자료공간 이외의 공간을 사용하지 않고 정렬한다.
단점
- 배열이 길어지면 효율이 떨어진다.
- 자료구조에 따라 역으로 정렬되어 있는 값들에 적용되면 최악의 성능을 보인다.
코드
관련 영상
시간 복잡도가 입력 자료의 구성에 따라 달라진다.
for i = 1 to n
정렬된 a[0]부터 a[i-1] 숫자 들과 차례대로 비교하여 a[i]보다 첫번째로 큰 수의 자리에 a[i] 값을 두고 그 자리부터 이후에 있는 값들의 인덱스를 뒤로 미뤄준다.
시간복잡도: O(n²)
장점
- 구현이 간단하다.
- 입력 자료가 정렬되어 있으면 있을 수록 빨라진다. 따라서 같은 시간복잡도를 가지는 다른 정렬(선택, 버블) 보다 효율이 높다.
- 같은 값인 경우 상대적 위치가 바뀌지 않는다. -> 안정한 정렬
- 주어진 자료공간 이외의 공간을 사용하지 않고 정렬한다.
단점
- 배열이 길어지면 효율이 떨어진다.
- 자료구조에 따라 역으로 정렬되어 있는 값들에 적용되면 최악의 성능을 보인다.
코드
숫자의 정렬 |
문자의 정렬 |
관련 영상
댓글 없음:
댓글 쓰기