선택 정렬 분석하기

선택 정렬은 배열의 인덱스를 반복합니다. 각 인덱스마다 indexOfMinimumswap을 호출합니다. 배열의 길이가 n n 이라면 배열에는 요소가 n n 개 있습니다.
선택 정렬은 반복문을 실행할 때마다 코드 두 줄을 실행하므로 총 2n2n줄의 코드를 실행한다고 생각할 수 있습니다. 하지만 사실은 다릅니다! indexOfMinimumswap은 함수입니다. 함수가 호출된다는 것은 여러 줄의 코드가 실행되는 것입니다.
swap을 한 번 호출할 때마다 몇 줄의 코드가 실행될까요? 일반적인 구현방법에서는 세 줄이 실행됩니다. 따라서 swap은 호출 때마다 항상 같은 시간이 소요됩니다.
그렇다면 indexOfMinimum은 한 번 호출할 때마다 몇 줄의 코드가 실행될까요? 이것을 알려면 indexOfMinimum 안에 반복문이 몇 개나 되는지 알아야 합니다. indexOfMinimum 호출에 반복문이 몇 번이나 실행될까요? 반복문이 반복되는 하위배열 구간의 크기를 알아야 합니다. 만일 하위배열의 범위가 배열 전체라면 (첫 번째 단계의 경우에 해당) 루프는 nn번 실행됩니다. 만일 하위배열의 크기가 6이면 루프는 6번 돌게 되는 것이죠.
예를 들어 배열 전체의 크기가 8일 때 선택 정렬이 어떻게 이루어질지 생각해봅시다.
  1. 첫 번째 indexOfMinimum 호출에서는 배열의 모든 값을 봐야 하기 때문에 indexOfMinimum의 반복문 내부는 총 8번 실행됩니다.
  2. 두 번째 indexOfMinimum호출에서는 하위 배열의 인덱스 1번부터 7번까지 봐야 하기 때문에 indexOfMinimum의 반복문 내부는 총 7번 반복됩니다.
  3. 세 번째 호출은 하위 배열의 인덱스 2번부터 7번까지 보기 때문에 반복문 내부는 총 6번 반복됩니다.
  4. 네 번째 호출에서는 하위 배열 내 인덱스 3번부터 7번까지 반복문 내부가 총 5번 반복됩니다.
  5. ...
  6. 마지막으로 indexOfMinimum의 여덟 번째 호출에서 반복문은 한 번만 돕니다.
이렇게 나오는 indexOfMinimum의 반복문이 실행되는 횟수는 총 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36번입니다.

알아두기: 1부터 nn까지 수의 합 계산하기

8 + 7 + 6 + 5 + 4 + 3 + 2 + 1을 어떻게 빠르게 계산할 수 있을까요? 수를 더하기 쉽게 다시 배열하면 계산이 더욱 쉬워집니다. 먼저 가장 큰 수와 가장 작은 수를 더해 8+1을 해봅시다. 둘의 합은 9 입니다. 이제 그 다음으로 큰 수와 그 다음으로 작은 수를 서로 더해 7+2를 합시다. 둘의 합도 역시 9입니다. 6+3은 어떨까요? 마찬가지로 9입니다. 마지막으로 5+4를 합니다. 또 9가 나왔습니다. 그럼 이제 답을 구해볼까요?
(8+1)+(7+2)+(6+3)+(5+4)=9+9+9+9=49=36 . \begin{aligned} (8 + 1) + (7 + 2) + (6 + 3) + (5 + 4) &= 9 + 9 + 9 + 9 \\ &= 4 \cdot 9 \\ &= 36 \ . \end{aligned}
방금 한 계산에서는 총 네 쌍의 수를 더해 각각의 합이 9가 되도록 만들었습니다. 이제 연속하는 정수의 합을 쉽게 계산하는 방법을 일반화시켜 봅시다.
  1. 가장 작은 수와 가장 큰 수끼리 짝지어 서로 더합니다.
  2. 짝지은 수의 개수로 곱해줍니다.
만일 수열안에 숫자가 홀수 개수만큼 밖에 없다면 어떻게 할까요? 상관없습니다! 홀로 남은 수는 한쌍의 반으로 취급하여 계산하면 됩니다. 예를 들어 1 + 2 + 3 + 4 + 5를 계산해야 한다면 합이 6인 두 쌍(1+5와 2+4)의 수와 남는 수 한 개(3)가 있어 총 2.5 쌍의 수가 나옵니다. 이를 계산해보면 2.56=15 2.5 \cdot 6 = 15 란 답을 얻을 수 있습니다.
1 부터 nn 까지 수의 합은 어떻게 구해야 할까요? 이와 같은 수열은 수학에서 등차급수라고 부릅니다. 여기서 가장 작은 수와 가장 큰 수의 합은 n+1n+1 입니다. 수가 총 nn 개 만큼 있으므로 n/2n/2 개의 쌍을 만들 수 있습니다 (nn은 홀수, 짝수 둘 다 가능). 따라서 1 부터 n 까지 수의 합은 (n+1)(n/2) (n + 1)(n / 2) 으로 나타내며 n2/2+n/2 n^2/2 + n/2 으로도 바꿔서 쓸 수 있습니다. 이 식에 n=5 n = 5 일 때와 n=8 n = 8 일 때를 대입해서 확인해보세요.

선택 정렬에 대한 점근적 실행 시간 분석하기

선택 정렬에 소요되는 총 실행 시간은 세 부분으로 나눌 수 있습니다.
  1. 모든 indexOfMinimum 호출에 대한 실행시간.
  2. 모든 swap 호출에 대한 실행시간.
  3. selectionSort함수 내 남아있는 나머지 반복문의 실행시간.
2번과 3번은 쉽습니다. swapnn번 호출되고 그때마다 같은 시간이 소요된다는 사실은 이미 알고 있습니다. 점근적 표기법 을 사용하면 swap을 호출하는데 Θ(n) \Theta(n) 의 시간이 걸리는 것 또한 알 수 있습니다. selectionSort에 있는 나머지 반복문은 단지 반복문 변수를 비교하여 약간씩 변화를 주거나 indexOfMinimumswap을 호출하는 것 밖에 없으므로 n n 번 반복되는 루프는 Θ(n) \Theta(n) 만큼의 시간이 걸릴 것으로 예측 가능합니다.
1번, 모든 indexOfMinimum 호출에 대한 실행시간에서 알아야 하는 부분 중 가장 까다로운 부분은 이미 알고 있습니다. indexOfMinimum의 반복문은 매번 같은 시간이 소요됩니다. 첫 번째 호출에서 이 루프는 n n 번 만큼 반복되며 그다음부터는 n1 n-1 , n2 n-2 , 이렇게 줄어듭니다. 바로 전에 배웠듯이 1+2++(n1)+n 1 + 2 + \cdots + (n-1) + n 이 등차급수며 일반항으로는 (n+1)(n/2) (n+1)(n/2) 또는 n2/2+n/2 n^2/2 + n/2 으로 나타낼 수 있습니다. 따라서 indexOfMinimum의 모든 호출에 따른 소요시간은 어떤 상수와 n2/2+n/2 n^2/2 + n/2 을 곱한 만큼입니다. Θ 표기법에서는 곱해주는 상수값이나 일반항에 들어간 1/2이나 하위항은 무시합니다. 결과적으로 모든 indexOfMinimum호출에 대한 실행시간은 Θ(n2) \Theta(n^2) 입니다.
위의 실행시간을 모두 더해보면, indexOfMinimum 호출에서 Θ(n2) \Theta(n^2) , swap 호출에서 Θ(n) \Theta(n) , selectionSort 에서 Θ(n) \Theta(n) , 이렇게 모두 세 개입니다. Θ(n2) \Theta(n^2) 항은 이 중에서도 가장 유효한 항이므로 선택 정렬의 실행시간은 Θ(n2) \Theta(n^2) 으로 정의할 수 있습니다.
또 알아야 할 것이 한가지 있습니다. 선택 정렬에서는 특별히 값이 바뀔만한 경우가 존재하지 않습니다. 입력값에 상관없이 indexOfMinimum 루프는 항상 n2+n/2 n^2 + n/2 번 반복됩니다. 따라서 선택 정렬의 실행 시간은 모든 경우에 Θ(n2) \Theta(n^2) 이라고 할 수 있습니다.
이제 Θ(n2) \Theta(n^2) 으로 얻은 값에 따라 실제 실행시간이 어떻게 바뀌는지 살펴봅시다. 선택 정렬이 nn개의 값을 정렬하는데 대략 n2/106 n^2/10^6 초가 걸린다고 가정해 봅시다. 초기 nn값을 작게 잡아 n=100 n = 100 으로 둡시다. 그렇다면 실제로 선택 정렬을 실행하는데 1002/106=1/100 100^2/10^6 = 1/100 초가 걸립니다. 매우 빠른 것 같지만 n=1000 n = 1000 일 때는 어떨까요? 이때는 10002/106=1 1000^2/10^6 = 1 초가 걸립니다. 배열은 10배 커졌지만, 실행 시간은 100배 길어졌습니다. n=1,000,000 n = 1{,}000{,}000 일 때는 선택 정렬을 하는데 1,000,0002/106=1,000,000 1{,}000{,}000^2/10^6 = 1{,}000{,}000 초, 일수로 계산하면 11.5 입니다. 배열의 크기를 1000배 늘리면 실행 시간은 백만 배나 늘어납니다!

위 자료는 다트머스 대학교 컴퓨터공학과토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.
로딩 중