[Sorting] 선택 정렬, Selection Sort

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- 선택 정렬 (Selection Sort)

• 리스트에서 아직 정렬되지 않은 부분의 원소들 중에서 최솟값을 선택하여 정렬되지 않은 부분의 가장 왼쪽의 원소와 교환하는 정렬 알고리즘
• 리스트의 앞쪽 부분은 정렬, 나머지 부분은 정렬이 되지 않은 상태로 마지막 한 개의 원소가 남을 때까지 반복적으로 수행

Selection sort, 출처 위키피디아

- 수행 시간

• 처음 루프가 수행될 때 n개의 원소들 중에서 최솟값을 찾기 위해 n - 1회의 원소 비교가 필요하고, 두 번째 루프에선 n - 1개의 원소들 중에서 n - 2회의 원소 비교가 필요, 즉 총 비교 횟수는 (n - 1) + (n - 2) + (n - 3) + ... + 2 + 1 = n(n - 1) / 2 = O(n^2) 소요
• 입력이 이미 정렬되어 있거나 역으로 정렬되어 있는 경우일지라도 항상 같은 시간 복잡도를 가짐
• 입력에 민감하지 않은(Input Insensitive) 알고리즘