4알고리즘 분석

 

자료를 크기 순서로 정렬하려면 반드시 두 수의 크기를 비교해야 합니다. 따라서 정렬 알고리즘의 계산 복잡도는 보통 비교 횟수를 기준으로 따집니다.

선택 정렬의 비교 방법은 문제 3의 동명이인 찾기에서 살펴본, 리스트 안의 자료를 한 번씩 비교하는 방법과 거의 같습니다. 따라서 이 알고리즘은 비교를 총 번 해야 하는 계산 복잡도가 O(n²)인 알고리즘입니다.

선택 정렬 알고리즘은 이해하기 쉽고 간단하여 많이 이용됩니다. 하지만 비교 횟수가 입력 크기의 제곱에 비례하는 시간 복잡도가 O(n²)인 알고리즘이므로 입력 크기가 커지면 커질수록 정렬하는 데 시간이 굉장히 오래 걸립니다.