2017년 10월 24일 화요일

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

앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 삽입하는 방식
시간 복잡도가 입력 자료의 구성에 따라 달라진다.







































for i = 1 to n
 정렬된 a[0]부터 a[i-1] 숫자 들과 차례대로 비교하여 a[i]보다 첫번째로 큰 수의 자리에  a[i] 값을 두고 그 자리부터 이후에 있는 값들의 인덱스를 뒤로 미뤄준다.

시간복잡도: O(n²)

장점
- 구현이 간단하다.
- 입력 자료가 정렬되어 있으면 있을 수록 빨라진다. 따라서 같은 시간복잡도를 가지는 다른 정렬(선택, 버블) 보다 효율이 높다.
- 같은 값인 경우 상대적 위치가 바뀌지 않는다. -> 안정한 정렬
- 주어진 자료공간 이외의 공간을 사용하지 않고 정렬한다.

단점
- 배열이 길어지면 효율이 떨어진다.
- 자료구조에 따라 역으로 정렬되어 있는 값들에 적용되면 최악의 성능을 보인다.

코드
숫자의 정렬

문자의 정렬
















관련 영상

댓글 없음:

댓글 쓰기