삽입 정렬(Insertion Sort)

삽입 정렬은 탐색하다가 정렬되지 않은 숫자가 발견되면 그 숫자를 알맞은 데 삽입해주는 것을 반복하는 정렬이다.

 

이 정렬은 정렬되지 않은 숫자가 나올 때까지 정렬하지 않고 탐색만 한다.

그렇기 때문에 최선의 경우(숫자가 이미 정렬되어 있는 경우)에는 매우 빠르다.

 

아래는 소스코드

 

 

다음은 말로 설명한 정렬의 단계이다.

 

1) 배열의 처음부터 끝까지 sp(Start Point의 약어)로 arr[sp]가 arr[sp+1]보다 작은지 탐색한다.

2) 만약에 arr[sp]가 arr[sp+1]보다 작으면 arr[sp+1]이 적당한 자리를 찾을 때까지 swap해준다.

3) 이 과정을 반복한다.

 

시간복잡도:

정렬이 모조리 되어있는 경우: O(n)

정렬이 하나도 되어있지 않은 경우: O(n^2)