이번에는 반복적인 방법으로 해결하는 버블 정렬 알고리즘을 살펴봅시다.
정렬 알고리즘은 배열의 자료를 원하는 순으로 배치하는 것을 말합니다. 이를 위해 입력 인자로 정렬할 자료들이 있는 배열의 시작 주소와 원소 개수, 비교 알고리즘을 전달합니다. 그리고 수행 후에는 배열 내의 자료들이 원하는 순서로 보관한 상태여야 합니다.
이 중에 버블 정렬은 앞에서부터 이웃하는 원소의 값을 비교하여 위치를 교환하는 것을 반복합니다. 이를 끝까지 수행하면 제일 큰 값이 맨 뒤에 위치합니다. 그리고 정렬할 개수를 1 줄인 후에 다시 반복합니다. 정렬할 원소의 개수가 1이면 모든 작업을 완료합니다.
버블 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복(i:=n; i>1 ; i:= i-1)
반복(j:=1; j<i ; j:=j+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:9, j:1)
2 9 4 1 5 6 8 3 7 (i:9, j:2)
2 4 9 1 5 6 8 3 7 (i:9, j:2) – 교환
2 4 9 1 5 6 8 3 7 (i:9, j:3)
2 4 1 9 5 6 8 3 7 (i:9, j:3) – 교환
2 4 1 9 5 6 8 3 7 (i:9, j:4)
2 4 1 5 9 6 8 3 7 (i:9, j:4) – 교환
2 4 1 5 9 6 8 3 7 (i:9, j:5)
2 4 1 5 6 9 8 3 7 (i:9, j:5) – 교환
2 4 1 5 6 9 8 3 7 (i:9, j:6)
2 4 1 5 6 8 9 3 7 (i:9, j:6) – 교환
2 4 1 5 6 8 9 3 7 (i:9, j:7)
2 4 1 5 6 8 3 9 7 (i:9, j:7) – 교환
2 4 1 5 6 8 3 9 7 (i:9, j:8)
2 4 1 5 6 8 3 7 9 (i:9, j:8) – 교환, 1회전 완료
2 4 1 5 6 8 3 7 9 (i:8, j:1)
2 4 1 5 6 8 3 7 9 (i:8, j:2)
2 1 4 5 6 8 3 7 9 (i:8, j:2) – 교환
2 1 4 5 6 8 3 7 9 (i:8, j:3)
2 1 4 5 6 8 3 7 9 (i:8, j:4)
2 1 4 5 6 8 3 7 9 (i:8, j:5)
2 1 4 5 6 8 3 7 9 (i:8, j:6)
2 1 4 5 6 3 8 7 9 (i:8, j:6) – 교환
2 1 4 5 6 3 8 7 9 (i:8, j:7)
2 1 4 5 6 3 7 8 9 (i:8, j:7) – 교환, 2회전 완료
2 1 4 5 6 3 7 8 9 (i:7, j:1)
1 2 4 5 6 3 7 8 9 (i:7, j:1) – 교환
…생략…
버블 정렬 알고리즘을 보면 반복문 내부에 반복문이 있는 구조입니다. 먼저 내부의 반복문에서 하는 일이 무엇인지 알아봅시다.
버블 정렬 알고리즘의 내부 반복문에서는 j값을 1부터 시작하여 i까지 순차적으로 증가하며 작업을 수행합니다. 따라서 루프 변성은 j값이 변하는 것입니다. 그리고 배열의 j 번째 요소와 앞의 요소를 비교하여 앞쪽 요소가 작으면 위치를 교환합니다. 이처럼 수행하면 배열의 맨 앞의 요소부터 j번째 요소 중에서 제일 큰 값은 j번째 요소입니다. 따라서 루프 불변성은 배열의 맨 앞의 요소부터 j번째 요소 중에서 제일 큰 값은 j번째에 있다는 것입니다.
루프 변성인 j값이 i전까지 변하는 특징과 루프 불변성인 컬렉션의 맨 앞의 요소부터 j번째 요소 중에 제일 큰 값은 j번째 있다는 특징으로 반복문을 수행하면 배열의 맨 앞에서 i전까지 요소 중에 제일 큰 값은 i전의 요소라고 말할 수 있습니다.
이번에는 내부 반복문을 감싸고 있는 외부 반복문을 살펴봅시다. i는 max에서 1보다 크면 1씩 감소하고 있습니다. 루프 변성을 보면 i는 max로 출발하므로 반복문을 한 번 수행하면 제일 큰 요소가 맨 뒤로 이동함을 알 수 있습니다. 그리고 i를 1씩 감소하면서 반복 수행하므로 언제나 i번째 요소 뒤에 있는 것들은 정렬 상태를 유지하고 i앞쪽의 요소보다 큰 값을 갖고 있음을 알 수 있습니다. 이러한 특징이 루프 불변성입니다.
따라서 루프 변성과 루프 불변성에 의해 위 알고리즘이 타당함을 알 수 있습니다.