[ 정렬 알고리즘 정의 ]
| 정렬 알고리즘 | 정의 |
| 버블(bubble) | 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 |
| 선택(selection) | 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 |
| 삽입(insertion) | 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 |
| 퀵(quick) | pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 |
| 병합(merge) | 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식 |
| 기수(radix) | 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식 |
여기서는 버블 정렬에 대해서 알아보자.
> 버블 정렬 (Bubble Sort)
- 버블 정렬은 두 인접한 데이터의 크기를 비교해 정렬하는 방법이다.
--> 인접한 두 원소를 비교하며, 큰 수를 계속하여 뒤로 보내 정렬하는 방식
- 오름 차순으로 정렬하는 경우 사용하는 정렬 방식이다.
* 원소들이 거품이 올라오는 것처럼 보인다 하여 거품 정렬(Bubble Sort)라고 이름을 지었다.
> 버블 정렬의 핵심 이론
* 루프(loop)를 돌면서 인접한 데이터 간의 swap 연산으로 정렬한다.
[ 버블 정렬 과정 ]
1. 비교 연산이 필요한 루프 범위를 설정한다.
2. 인접한 두개의 데이터 값을 비교한다.
3. swap 조건에 부합하면 swap 연산을 수행한다.
4. 루프 범위가 끝날 때까지 2~3번을 반복한다.
5. 정렬 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외한다.
6. 비교 대상이 없을 때까지 1~5번을 반복한다.
* 만일 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면
그 영역 뒤에 있는 데이터가 모두 정렬되었다는 뜻이므로 모든 과정을 종료해도 된다.
> 버블 정렬의 시간 복잡도
- 직관적으로 이해가 쉬운 정렬로 간단하게 구현할 수 있지만 일반적인 시간 복잡도는 O(n^2)으로
다른 정렬 알고리즘보다 속도가 느린 편이다. 시간 복잡도 O(n^2)의 총 반복 횟수는 n(n-1)/2가 된다.
- 가장 큰 수를 뒤로 보내는 방식을 사용하기 때문에,
이미 정렬하고자 하는 배열이 어느정도 정렬이 되어 있는 상태 일수록 최선의 성능을 낼 수 있다.
- 버블정렬은 속도가 느린편이라 실전에서 거의 사용할 일은 없지만,
버블 정렬에서 사용되는 Swap 연산이 중요하기 때문에 초기 프로그래밍시 자주 사용되는 예제 중 하나이다.
[ 참고 링크 ]
'자료구조' 카테고리의 다른 글
| 선택 정렬(Selection Sort) (0) | 2023.01.31 |
|---|---|
| 스택과 큐 (Stack and Queue) (0) | 2023.01.17 |
