이번에는 순차 정렬 알고리즘의 타당성 및 수행 속도를 계산해 보기로 해요.
순차 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복(i:=0->n)
반복(j:=i+1->n)
조건(compare(base[i], base[j]) > 0)
교환(base[i],base[j])
순차 정렬의 내부 반복문은 j값이 i+1에서 n까지 변하죠. 그리고 i번째와 j번째 요소와 비교하여 i번째 원소가 크면 교환하기 때문에 i번째에서 j번째 원소 중에 제일 작은 값은 언제나 i번째에 존재합니다. 따라서 내부 반복문을 수행하면 i에서 마지막 원소 중에 제일 작은 값이 i번째에 배치함을 알 수 있어요.
외부 반복문은 i값이 0에서 n까지 변하죠. 그리고 내부 반복문을 통해 i번째에서 마지막 원소 중에 제일 작은 원소를 i번째에 배치하므로 i번 앞에 있는 원소는 정렬 상태를 유지합니다. 따라서 루프 변성인 i가 n까지 변하는 성질과 루프 불변성인 i번째 앞에 있는 원소는 정렬 상태를 유지한다는 특징을 통해 위 알고리즘을 수행하면 정렬할 수 있음을 알 수 있습니다.
이번에는 수행 속도를 접근식 표기 방식으로 계산해 보아요.
내부 반복문을 수행하는 시간을 S(i, n)이라고 하면 n-i 번 비교하고 교환 횟수는 최악일 때 n-i번이예요. 따라서 S(i, n) <= n-i(비교횟수) + n-2(최악의 교환 횟수) = 2(n-i)
외부 반복문은 i가 0~n-1까지 변하면서 내부 반복문을 수행합니다. 따라서 외부 반복문을 수행하는데 걸리는 시간을 T(n)이라고 하면 S(0,n)+S(1,n)+…+S(n-1,n)입니다.
T(n) = S(0,n) + S(1,n) + … + S(n-1,n) = 2n + 2(n-1) + … + 2
따라서 다음과 같이 표현할 수 있어요.
T(n) = 2n + 2(n-1) + … + 2
T(n) = 2 + … + 2(n-1) +2n
따라서 2T(n) = 2(n+1) + 2(n+1) + 2(n+1)
T(n) = (n+1) + (n+1) +… +(n+1)
n+1을 n번 더한 값이므로 T(n) = n(n+1) = n^2 + n 입니다.
점근식 표기에서는 가장 높은 차수의 항만 사용하고 상수를 버리므로 O(n^2)입니다.