삽입정렬

삽입정렬 (Insertion Sort)

• 2번째 원소부터 시작해서 그 앞의 원소들과 값을 비교해 위치를 정한 뒤, 중간에 있는 원소들을 모두 뒤로 한칸씩 이동시킨 후 삽입하는 알고리즘

시간복잡도

• 최선의 경우 : O(N) - 모두 정렬이 되어 있을 경우 한번씩만 비교한다
• 평균, 최악의 경우 : O(N^2)

장점

1. 정렬이 어느정도 되어 있는 경우일수록 효율적이다
2. 별도의 메모리 공간이 필요없다 (제자리 정렬)
3. 안정 정렬이다

단점

1. 배열이 길어질수록 비효율적이다

선택 정렬과의 차이

- 선택 정렬은 선택 원소 뒤의 값을 무조건 모두 비교하지만, 삽입정렬은 필요한 만큼만 비교를 하기 때문에 더 효율적이다.

 

참고 - Gyoogle