지금까지는 주로 최악의 시나리오에서 얼마나 많은 단계가 걸리는지에 초점을 맞췄다. 하지만 최악의 시나리오 외에도 고려할 가치가 있는 상황들이 있다.

6-1 삽입 정렬

삽입 정렬을 배우면서 최악의 경우가 아닌 다른 시나리오를 분석하는 것에 어던 장점이 있는지 알아보자.

1. 첫 번재 패스스루에서 임시로 인덱스 1 (두 번째 셀)의 값을 삭제하고 이 값을 임시 변수에 저장한다. 값이 없어졌으므로 공백이 생긴다.
2. 다음으로 공백 왼족에 있는 값을 가져와 임시 변수에 있는 값과 비교하는 시프트 단계를 시작한다. 공백 왼쪽에 있는 값이 임시 변수에 있는 값보다 크면 그 값을 오른쪽으로 시프트한다. 값을 오른쪽으로 시프트 했으므로 자연히 공백이 왼족으로 옮겨진다. 임시로 삭제한 값보다 작은 값을 만나거나 배열의 왼쪽 끝에 도달해야 시프트 단계가 끝난다.
3. 임시 변수 값을 공백에 삽입한다.
4. 1 ~ 3단계가 하나의 패스스루다. 배열의 마지막 인덱스에서 패스스루를 시작할 때 까지 패스스루를 반복한다.

6-2 삽입 정렬 실제로 해보기

배열 [4, 2, 7, 1, 3]을 삽입 정렬해 보자.

1. 인덱스 1의 2를 삭제하고 tempValue라는 변수에 저장한다.
2. 4와 tempValue를 비교한다.
3. 4가 tempValue보다 크므로 4를 오른쪽으로 시프트 한다. 공백이 배열의 왼쪽 끝에 있으므로 더 이상 왼쪽으로 시프트할 수 없다.
4. tempValue를 다시 배열에 삽입해서 첫 번째 패스스루를 끝낸다. [2, 4, 7, 1, 3]
5. 두 번째 패스스루는 인덱스 2의 7을 삭제하고 tempValue 변수에 저장한다.
6. 4와 tempValue를 비교한다. 4가 더 작으므로 시프트하지 않는다. tempValue보다 작은 값을 만났으므로 시프트 단계가 끝난다.
7. tempValue를 다시 배열에 삽입해서 두 번째 패스스루를 끝낸다. [2, 4, 7, 1, 3]
8. 인덱스 3의 1을 삭제하고 tempValue 변수에 저장한다.
9. 7과 tempValue를 비교한다.