[C++] 정렬 #1 버블 정렬 & 선택 정렬 (Bubble Sort & Selection Sort)
목차
1. 정렬 알고리즘
- 원소들을 번호 순이나 사전 순 같이 일정한 순서로 열거하는 알고리즘
- 다른 알고리즘을 수행 하기 전 최적화를 위해 우선적으로 실행한다.
- 대표적인 정렬 알고리즘 6개가 존재한다.
ㄴ 버블 정렬, 선택 정렬, 삽입 정렬, 힙 정렬, 병합 정렬, 퀵 정렬
※ 시간 복잡도
| Sorting | Best | Avg | Worst |
| 버블 정렬 | O(n²) | O(n²) | O(n²) |
| 선택 정렬 | O(n²) | O(n²) | O(n²) |
| 삽입 정렬 | O(n) | O(n²) | O(n²) |
| 힙 정렬 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) |
| 병합 정렬 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) |
| 퀵 정렬 | O(nlog₂n) | O(nlog₂n) | O(n²) |
2. 버블 정렬 (Bubble Sort)
- 서로 인접한 두 원소를 검사하여 정렬.
- 1회전 마다 정렬되지 않은 배열에서 최대(내림차순이라면 최소)값을 하나씩 정렬해나간다.
- 정렬 과정이 마치 거품이 올라오는 것 처럼 보여 버블 정렬이라 한다.
- 시간 복잡도가 O(n²)으로 느리다.
가. 구현하기
3. 선택 정렬 (Selection Sort)
- 정렬할 구간에서 가장 작은 값을 찾아 맨 앞과 위치를 교환하여 정렬. (내림차순이라면 가장 큰 값)
- 1회전 마다 정렬되지 않은 배열의 최소(내림차순 이라면 최대) 값이 하나씩 정렬된다.
- 정렬할 원소를 선택하기 때문에 선택 정렬이라 한다.
- 시간 복잡도가 버블 정렬과 같은 O(n²) 이지만 버블 정렬보다 항상 빠르다.
ㄴ 정렬한 구간에서의 가장 작은 값(큰 값)을 제외 시키는데 버블 정렬은 여러번 swap를 해야하지만 선택 정렬은 단 한번의 swap이면 1회전이 가능하기 때문
가. 구현하기
※ 참조
위키 백과 버블 정렬
https://ko.wikipedia.org/wiki/%EB%B2%84%EB%B8%94_%EC%A0%95%EB%A0%AC
위키 백과 선택 정렬
https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC