Study/Algorithm

[정렬] 선택 정렬(Selection Sort)

- 선택 정렬의 원리는 입력 원소들 중에서 최대 원소를 선택한다. - 이 최대 원소를 제외한 나머지 입력 원소들 중 최대 원소를 선택한다. - 이러한 작업을 반복한다. 이처럼 최대 원소를 찾아 가장 마지막 원소와 교환한다. 다음은 선택 정렬 알고리즘이다. selectionSort(A[], n) { for last ← downto 2 { // 1 A[1...last] 중 가장 큰 수 A[k]를 찾는다 // 2 A[K] ↔ A[last]; A[k]와 A[last]값을 교환 // 3 } } - 1의 for 루프는 n-1번 반복한다. - 2에서 가장 큰 수를 찾기 위한 비교 횟수 = 첫 번째 반복 시 n-1, 두 번째 반복 시 n-2,..., n-2번째 반복시 2, n-1번째 반복시 1 => 이 비교하는 횟수가..