선택 정렬 의사코드

카드를 정렬하는 방법에는 여러가지가 있습니다. 선택 정렬이라는 간단한 방법이 있습니다. 위에서 정렬한 방법과 비슷하죠:

이 알고리즘에서는 다음으로 작은 항목을 선택하고 이를 제자리로 바꾸는 과정을 반복하기 때문에 선택 정렬이라고 부릅니다.

이 알고리즘을 아래에서 스스로 확인해볼 수 있습니다. "Step"을 이용하여 알고리즘의 각 단계를 알아본 후 모든 단계를 이해하게 되면 "Play"를 눌러 보세요.

스스로 확인해 보니 이 알고리즘이 어떻다는 생각이 드시나요? 어느 부분이 가장 오래 걸린 것 같나요? 이 알고리즘이 규모가 큰 배열에서 잘 작동할 것이라고 생각하나요? 이 알고리즘을 구현하면서 이런 의문점을 계속 염두에 두시기 바랍니다.

선택 정렬의 한 단계는 다음으로 작은 카드를 찾아서 이를 올바른 위치로 갖다 놓는 과정입니다. 예를 들어 초기 배열이 [13, 19, 18, 4, 10] 였다면 배열 내에서 가장 작은 값의 인덱스를 우선 찾아야 합니다. 4가 가장 작은 값이므로 가장 작은 값의 인덱스는 3입니다.

선택 정렬은 인덱스 3에 있는 값과 인덱스 0의 값을 바꾸어 [4, 19, 18, 13, 10]가 됩니다. 이제 두 번째로 작은 값의 인덱스를 찾아 이를 인덱스 1의 값과 바꾸어야 합니다.

array에서 두 번째로 작은 값의 인덱스를 찾는 코드를 작성하는 것이 복잡할 수도 있습니다. 여러분은 분명 잘 하겠지만 더 좋은 방법이 있습니다. 가장 작은 값은 이미 인덱스 0과 바뀌었기 때문에 사실은 인덱스 1부터 시작하는 배열의 일부분에서 가장 작은 값을 찾아내야 합니다. 이를 하위 배열에서의 선택이라고 합니다. 그러므로 이 경우 인덱스 1에서 시작하는 하위 배열에서 가장 작은 값을 가지는 인덱스를 찾아야 하는 것이죠. 위의 예에서 배열 전체가 [4, 19, 18, 13, 10] 이라면 인덱스 1에서 시작하는 하위 배열에서 가장 작은 값은 10이고 인덱스 값은 원래 배열 내에서 4입니다. 그러므로 인덱스 4는 전체 배열에서 두 번째로 작은 요소입니다.

다음 응용에서 이 전략을 이용해 보세요. 이것만 할 수 있다면 전체 선택 정렬 알고리즘에서 여러분이 구현해야 할 대부분을 해결한 셈입니다.

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