가장 고전적이고 떠올리기 쉬운 정렬 알고리즘 입니다.

• C 언어 구현
• Python 구현

1. 배열을 순회하며 가장 작은 값을 찾습니다.
2. 가장 작은 값의 인덱스와 바꿀 자리의 인덱스를 서로 교환합니다
3. 이를 반복합니다

https://hongcoding.tistory.com/181

공간복잡도

: O(N)

다른 배열을 만들거나 사용하지 않으므로 생성되는 공간은 오직 배열의 크기와 같습니다. 이때 교환을 위해 생성되는 크기 1 (temp) 이 있지만 배열이 커질 때 이는 무시 할 수 있을 작은 숫자이므로 O(N)으로 표현됩니다.

시간 복잡도

: Best O(N), Worst O(N^2), AVG O(N^2)

배열의 각 자리마다 (전체 배열 크기)-(현재 인덱스) 만큼 순회하며 비교하므로

$$ \sum_{k=1}^{n-1} {(n-k)} = \frac {n(n-1)}{2} $$

의 비교 횟수를 가지고, $\lim_{n \to \infty} \frac{n(n-1)}{2}$ 를 생각하면 분모의 -1과 1/2는 무시할 수 있으므로 시간 복잡도는 O(N^2)으로 표현됩니다.