선택정렬

선택정렬은 기본적으로 자료의 선택과 교환 연산으로 이루어져 있다. 다만 이러한 선택과 교환 연산을 자료의 개수대로 n 번만큼 루프를 돌면서 실행한다, 따라서 선택 정렬이 두개의 루프를 돌면서 실행하는 비교 연산의 전체 횟수는 아래와 같이 계산할 수 있다. O((n-1) + (n-2) + ... + 3 + 2 + 1) = O(n(n-1) / 2) = O(n²) 또한 이때 실행되는 자료의 교환 횟수는 바깥 루프의 횟수와 같다. 다만 각 교환마다 3번의 이동 연산이 필요하기 때문에 전체 이동 연산의 횟수는 아래와 같다. O(3(n-1)) = O(n) 최종적으로 선택정렬의 효율성은 앞의 비교 연산과 이동 연산의 합으로 구하므로, 이 경우 O(n²) 이 된다. O(n² + n) = O(n²) 선택정렬