버블, 선택, 삽입 정렬 정리

1. 버블 정렬

최상의 경우 시간 복잡도
- 이미 정렬된 상태일 때 최상의 경우
- 정렬되지 않은 영역을 순차적으로 탐색 후 swap이 한번도 일어나지 않으면 정렬 종료
- 원소 개수 $n$이 증가할 때 수행 시간이 증가한다
- 시간 복잡도: $O(n)$
최악의 경우 시간 복잡도
- 내림차순으로 정렬된 경우
- 인덱스 $k$의 자리를 정렬된 상태로 만들기 위해선 $k$번의 비교가 필요하다
- 마지막 인덱스 자리부터 인덱스 1번 자리까지 정렬된 상태로 만들면 모든 원소가 정렬된다
- 원소 개수를 $n$이라고 할 때 비교 횟수는
$$ \sum_{k=1}^{n - 1}k = \frac{n(n-1)}{2} $$
- 시간 복잡도: $O(n^2)$
공간 복잡도
- 원소 개수가 늘어나도 필요한 메모리 크기는 같다
- 공간 복잡도: $O(1)$

작은 값부터 정렬된다
한 원소를 정렬할 때 swap은 한 번만 일어난다
unstable 정렬이다
- ex) $(2, a), (2, b), (1, c)$일 때 숫자 기준으로 선택 정렬하면 $(1, c), (2, b), (2, a)$가 된다

최상의 경우
- 이미 원소들이 정렬된 경우
- 각 원소를 정렬된 자리에 있는지 한번 씩만 확인 후 수행 종료
- 원소 개수 $n$이 증가하면 수행 시간이 증가
- 시간 복잡도: $O(n)$
최악의 경우
- 내림차순으로 정렬된 경우
- 원소 개수가 $n$개이고 인덱스 1번부터 $n - 1$번 원소의 삽입 위치를 찾기 위한 총 비교 횟수는 $1 + 2 + 3 + ... + (n - 1)$이므로
$$ \sum_{k=1}^{n - 1}k = \frac{n(n-1)}{2} $$
- 시간 복잡도: $O(n^2)$
공간 복잡도
- 원소 개수가 늘어나도 필요한 메모리 크기는 같다
- 공간 복잡도: $O(1)$