선택 정렬 분석하기

선택 정렬 배열의 인덱스에서 루프하는 정렬 방법의 하나입니다. 선택 정렬은는 인덱스 하나를 만날 때마다 indexOfMinimum, swap을 호출합니다. 배열의 길이가 n 이면 배열에는 n 개의 인덱스가 있습니다.
선택 정렬은 루프를 실행할 때마다 코드 두 줄을 실행하므로 총 2, n 번 만큼 코드를 실행한다고 생각할 수 있습니다. 하지만 사실은 다릅니다! indexOfMinimumswap은 함수입니다. 두 함수 모두 호출되어도 일부 코드만 실행됩니다.
swap을 한 번 호출할 때마다 몇 줄의 코드가 실행될까요? 일반적인 구현방법에서는 세 줄이 실행됩니다. 따라서 swap은 호출 때마다 항상 같은 시간이 소요됩니다.
그렇다면 indexOfMinimum은 한 번 호출할 때마다 몇 줄의 코드가 실행될까요? 이것을 알려면 indexOfMinimum 안에 루프가 몇 개나 되는지 알아야 합니다. indexOfMinimum 호출에 루프가 몇 번이나 실행될까요? 이것을 알려면 루프가 반복되는 하위배열 구간의 크기를 알아야 합니다. 만일 하위배열의 범위가 배열 전체라면 (첫 번째 단계의 경우에 해당) 루프는 n번 실행됩니다. 만일 하위배열의 크기가 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 부터 n 까지 수의 합 계산하기

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, point, 5, dot, 6, equals, 15 이와 같은 답을 얻을 수 있습니다.
1 부터 n 까지 수의 합은 어떻게 구해야 할까요? 이와 같은 수열은 수학에서 등차급수라고 부릅니다. 여기서 가장 작은 수와 가장 큰 수의 합은 n, plus, 1 입니다. 수가 총 n 개 만큼 있으므로 n, slash, 2 개의 쌍을 만들 수 있습니다 (n은 홀수, 짝수 둘 다 가능). 따라서 1 부터 n 까지 수의 합은 left parenthesis, n, plus, 1, right parenthesis, left parenthesis, n, slash, 2, right parenthesis 으로 나타내며 n, start superscript, 2, end superscript, slash, 2, plus, n, slash, 2 으로도 바꿔서 쓸 수 있습니다. 이 식에 n, equals, 5 일 때와 n, equals, 8일 때를 대입해서 확인해보세요.

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

선택 정렬에 소요되는 총 실행 시간은 세 부분으로 나눌 수 있습니다.
  1. 모든 indexOfMinimum호출에 대한 실행시간.
  2. 모든 swap호출에 대한 실행시간.
  3. selectionSort함수 내 남아있는 다른 모든 루프의 실행시간.
2번과 3번은 쉽습니다. swapn 번 만큼 호출되고 때마다 같은 시간이 소요된다는 사실은 이미 알고 있습니다. 점근적 표기법 을 사용하면 swap을 호출하는데 Θ(n) \Theta(n) 만큼의 시간이 걸리는것 또한 알 수 있습니다. selectionSort 에 있는 나머지 루프들은 단지 루프 변수를 비교하여 약간 씩 변화를 주거나 indexOfMinimumswap을 호출하는 것 밖에 없으므로 n 번 반복되는 루프는 Θ(n) \Theta(n) 만큼의 시간이 걸리는 것을 충분히 예측 가능합니다.
1 모든 indexOfMinimum 호출에 대한 실행시간에서 알아야 하는 부분 중 가장 까다로운 부분은 이미 알고 있습니다. indexOfMinimum 의 루프는 매번 같은 시간이 소요됩니다. 첫 번째 호출에서 이 루프는 n번 만큼 반복되며 그다음부터는 n, minus, 1, n, minus, 2 이렇게 줄어듭니다. 바로 전에 배웠듯이 1+2++(n1)+n 1 + 2 + \cdots + (n-1) + n 이 등차급수며 일반항을 left parenthesis, n, plus, 1, right parenthesis, left parenthesis, n, slash, 2, right parenthesis 또는 n, start superscript, 2, end superscript, slash, 2, plus, n, slash, 2 으로 나타낼 수 있습니다. 따라서 indexOfMinimum 의 모든 호출에 따른 소요시간은 어떤 상수와 n, start superscript, 2, end superscript, slash, 2, plus, n, slash, 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 루프는 항상 n, start superscript, 2, end superscript, plus, n, slash, 2 번 반복됩니다. 따라서 선택 정렬을 모든 경우에 Θ(n2) \Theta(n^2) 번 만큼 실행된다고 할 수 있습니다.
이제 Θ(n2) \Theta(n^2) 으로 얻은 값에 따라 실제 실행시간이 어떻게 바뀌는지 살펴봅시다. 선택 정렬이 n 개의 값을 정렬하는데 대략 n, start superscript, 2, end superscript, slash, 10, start superscript, 6, end superscript 초가 걸린다고 가정해봅시다. 초기 n 값을 작게 잡아 n, equals, 100으로 둡시다. 그렇다면 실제로 선택 정렬을 실행하는데 100, start superscript, 2, end superscript, slash, 10, start superscript, 6, end superscript, equals, 1, slash, 100 초가 걸립니다. 매우 빠른 것 같지만 n, equals, 1000일 때는 어떨까요? 이때는 1000, start superscript, 2, end superscript, slash, 10, start superscript, 6, end superscript, equals, 1 초가 걸립니다. 배열은 10배 커졌지만, 실행시간은 100배 길어졌습니다. n, equals, 1, comma, 000, comma, 000일 때는 선택 정렬을 하는데 1, comma, 000, comma, 000, start superscript, 2, end superscript, slash, 10, start superscript, 6, end superscript, equals, 1, comma, 000, comma, 000 초, 일수로 계산하면 11.5 입니다. 배열의 크기를 1000배 늘리면 실행시간은 백만 배나 늘어납니다!

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