[자바 Do It! 알고리즘]Chapter06 정렬 (단순삽입정렬)

[단순삽입정렬]

1. 단순삽입정렬은 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입하는'작업을 반복하여 정렬하는 알고리즘입니다.

2. 단순 삽입정렬은 2번째 요소부터 선택하여 진행합니다.

3. 정렬된 부분과 아직 정렬되지 않은 부분에서 배열이 다시 구성된다고 생각하면서 아래의 작업을 n-1회 반보갛면 정렬을 마치게 됩니다.

1) 아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입합니다.

2) '알맞은 위치'란 왼쪽에 이웃한 요소가 선택한 요소보다 크면 그 값을 대입하고 앞으로 이동하면서 이 작업을 반복합니다. 그러다가 선택한 값 이하의 요소를 만나면 그보다 앞쪽은 검사할 필요가 없으므로 해당 위치에 삽입할 값을 대입합니다.

3) 즉, tmp에 a[i]를 대입하고 반복 제어용 변수 j에 i-1을 대입한 다음 아래의 두 조건 중 하나를 만족할 때까지 j를 1씩 감소하면서 대입하는 작업을 반복합니다.

(1) 정렬된 열의 왼쪽 끝에 도달합니다.

(2) tmp보다 작거나 같은 key를 갖는 항목 a[j]를 발견합니다.

4) 이때 드모르간 법칙을 적용하면 아래의 두 조건이 모두 성립할 때까지 반복한다고 할 수 있습니다.

(1) j가 0보다 큽니다.

(2) a[j - 1] 값이 tmp보다 큽니다.

(드모르간 법칙은 챕터1에 나왔었는데, 아직도 잘 모르겠습니다.. 3), 4) 번 내용은 어렵네요..)

​

이렇게 구현한 단순 삽입 정렬 알고리즘은 떨어져 있는 요소들이 서로 뒤바뀌지 않아 안정적입니다.

요소의 비교횟수와 교환횟수는 n2/2회입니다.

​