이번에는 거품 정렬 알고리즘의 타당성 및 수행 속도를 계산해 보기로 해요.
거품 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복(i:=n->1)
반복(j:=1->i)
조건(compare(base[j-1], base[j]) > 0)
교환(base[j-1],base[j])
거품 정렬 알고리즘을 보면 반복문 내부에 반복문이 있는 구조입니다. 먼저 내부의 반복문에서 하는 일이 무엇인지 알아봅시다.
거품 정렬 알고리즘의 내부 반복문에서는 j값을 1부터 시작하여 i까지 순차적으로 증가하며 작업을 수행하죠. 따라서 루프 변성은 j값이 변하는 것이예요. 그리고 배열의 j번째 요소와 j번째 앞의 요소와 비교하여 앞쪽 요소가 작으면 위치를 교환합니다. 이처럼 수행하면 배열의 맨 앞의 요소부터 j번째 요소 중에서 제일 큰 값은 j번째 요소가 되죠. 따라서 루프 불변성은 배열의 맨 앞의 요소부터 j번째 요소 중에서 제일 큰 값은 j번째에 있다는 것이예요.
루프 변성인 j값이 i전까지 변하는 특징과 루프 불변성인 맨 앞의 요소부터 j번째 요소 중에 제일 큰 값은 j번째 있다는 특징으로 인해 반복문을 수행하면 배열의 맨 앞에서 i-1 번째 요소 중에 제일 큰 값은 i-1 번째 요소라고 말할 수 있어요.
이번에는 내부 반복문을 감싸고 있는 외부 반복문을 살펴보아요. i는 max에서 1보다 크면 1씩 감소하고 있어요. 내부 반복문을 수행하면 제일 큰 값이 i-1번째로 이동하기 때문에 1회전에서 최대값은 n-1번째인 마지막에 배치합니다. 다시 i를 1 감소한 후에 내부 반복문을 수행하면 그 다음 최대값이 n-2번째에 배치합니다. 따라서 i번째 이후의 원소들은 언제나 정렬 상태를 유지하고 i번 앞쪽의 요소보다 큰 값을 갖고 있음을 알 수 있어요. 이러한 특징이 루프 불변성이예요.
결국 루프 변성이 i가 1까지 가므로 루프 불변성 i 이후의 원소는 정렬 상태이고 앞쪽의 요소보다 큰 값을 갖는다는 규칙에 의해 위 알고리즘이 타당함을 알 수 있어요.
이번에는 거품 정렬 알고리즘 성능을 분석합시다.
거품 정렬의 내부 반복문의 수행 시간을 S(i)라고 가정할게요. 내부 반복문은 j가 1에서 i이전까지 순차적으로 증가하므로 비교를 i-1번, 교환을 최악일 때 i-1번 한다고 볼 수 있어요. 따라서 S(i)= i-1이죠.
외부 반복문은 i가 n에서 1로 역순으로 감소하면서 내부 반복문을 수행합니다. 수행 시간을 T(n)이라 가정하면 T(n) = S(n) + S(n-1) + S(n-2) + … +1 이죠.
따라서 T(n) = S(n) + S(n-1) + … +S(2) + S(1) = n-1 + n-2 + …. + 1 + 0
따라서 T(n)= n(n-1)/2 이고 점근식 표기에서 높은 차수의 항만 남고 상수를 버리므로 O(n^2)라고 할 수 있습니다. 거품 정렬도 순차 정렬처럼 O(n^2)이네요.