이번에는 반복적인 방법으로 해결하는 삽입 정렬(Insertion Sort) 알고리즘을 살펴볼게요.
삽입 정렬도 순차 정렬처럼 맨 앞에서부터 정렬 범위를 확장해 나가는 알고리즘이예요. 차이점은 확장할 범위의 끝에 있는 원소를 앞의 원소와 비교하며 자신보다 크면 위치를 바꾸고 그렇지 않으면 반복을 멈춘다는 것이죠. 순차 정렬에서 확장할 위치에 배치할 원소를 뒤쪽 원소와 비교하며 교환했지만 삽입 정렬에서는 확장할 위치에 있는 원소를 앞의 원소와 비교하며 교환하며 자신의 위치를 찾는다는 것이 다릅니다.
삽입 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복(i:=1->n)
반복(j:=i->1)
조건(compare(base[j-1], base[j]) > 0)
교환(base[j-1],base[j])
조건이 거짓일 때
내부 반복문 탈출
예:
2 9 4 1 5 6 8 3 7 (정렬 전, n:9)
2 9 4 1 5 6 8 3 7 (i:1, j:1), 1회전 완료
2 9 4 1 5 6 8 3 7 (i:2, j:2)
2 4 9 1 5 6 8 3 7 (i:2, j:2), 교환
2 4 9 1 5 6 8 3 7 (i:2, j:1), 내부 반복문 탈출, 2회전 완료
2 4 9 1 5 6 8 3 7 (i:3, j:3)
2 4 1 9 5 6 8 3 7 (i:3, j:3), 교환
2 4 1 9 5 6 8 3 7 (i:3, j:2)
2 1 4 9 5 6 8 3 7 (i:3, j:2), 교환
2 1 4 9 5 6 8 3 7 (i:3, j:1)
1 2 4 9 5 6 8 3 7 (i:3, j:1), 교환, 3회전 완료
1 2 4 9 5 6 8 3 7 (i:4, j:4)
1 2 4 5 9 6 8 3 7 (i:4, j:4), 교환
1 2 4 5 9 6 8 3 7 (i:4, j:3), 내부 반복문 탈출, 4회전 완료
1 2 4 5 9 6 8 3 7 (i:5, j:5)
1 2 4 5 6 9 8 3 7 (i:5, j:5), 교환
1 2 4 5 6 9 8 3 7 (i:5, j:4), 내부 반복문 탈출, 5회전 완료
1 2 4 5 6 9 8 3 7 (i:6, j:6)
1 2 4 5 6 8 9 3 7 (i:6, j:6), 교환
1 2 4 5 6 8 9 3 7 (i:6, j:5), 내부 반복문 탈출, 6회전 완료
1 2 4 5 6 8 9 3 7 (i:7, j:7)
1 2 4 5 6 8 3 9 7 (i:7, j:7), 교환
1 2 4 5 6 8 3 9 7 (i:7, j:6)
1 2 4 5 6 3 8 9 7 (i:7, j:6), 교환
1 2 4 5 6 3 8 9 7 (i:7, j:5)
1 2 4 5 3 6 8 9 7 (i:7, j:5), 교환
… 생략 …