1. 버블 정렬 (Bubble Sort) 또는 교환 정렬 (Exchange Sort)
ㅇ 정렬 방법
- 이웃 요소 간에 대소 비교하고, 필요시 교환을 수행하며,
- 이 과정을 전체 자료에 걸쳐 반복 수행
ㅇ 버블 의미(어원)
- 매 반복/패스/라운드 마다, 가장 큰 수가 버블(거품)되어 맨 끝으로 이동됨
ㅇ 한편, 교환 정렬 (Exchange Sort)은, 버블 정렬과 거의 같으나,
- 두 이웃 수 간에 비교 및 교환이 아니라,
- 두 수의 위치 중 하나를 고정하고 다른 위치를 이동하며 비교/교환을 수행
2. 연산의 구성 및 계산 효율성
ㅇ 연산 및 구성
- 연산 : 비교(compare), 교환(swap)
- 구성 : 이중 루프(반복문)
ㅇ 계산 효율성 : O(n2) ☞ 평방시간 참조
- 키 비교 횟수 : 총 n(n-1)/2 회
. i=0일 때, (n-1)번 비교, i=1일 때, (n-2)번 비교, ... , i=(n-2)일 때, 1번 비교 등
. 즉, (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2
* 버블 정렬은, 항상 O(n2)인, 가장 느린 정렬 알고리즘 임
3. 알고리즘 설명 및 특징
ㅇ 2개의 중첩 루프를 사용
- 외부 루프는, 루프를 돌 때 마다,
. 정렬 대상 크기를 하나씩 줄임
- 내부 루프는,
. 좌측부터 두 이웃 원소를 비교하며, (비교)
. 순서가 맞지 않으면, 하나하나 교환하고 나감 (교환)
. 결국, 가장 큰 원소를 맨 우측에 보냄
ㅇ 구현이 매우 단순하나,
- 알려진 정렬 알고리즘 중 가장 비효율적인 성능을 보임
ㅇ 다만, 기 정렬 여부의 확인이 가능
- 만일, 어떤 교환도 발생 않고 끝나면,
- 이미 자료가 정렬된 상태 임 ☞ 3.항 개선 버블 정렬 참조
4. 알고리즘 표현 (오름차순 기준)
ㅇ 개선전 버블 정렬
Input : (정렬 전 데이터 배열) Data[], (배열 데이터 수) int n
Output : (정렬 후 데이터 배열) Data[]
BubbleSort(int Data[], int n) {
for (i = 0; i < n-1; i++) // (입력 개수 - 1)까지 반복
for (j = 0; j < n - (i+1); j++) // (대상 개수 - 1)까지 반복
if (Data[j] > Data[j+1]) // 순서 맞지 않으면 (비교)
Data[j] ↔ Data[j+1]; // 자리바꿈 (교환)
}
ㅇ 개선후 버블 정렬
Input : (정렬 전 데이터 배열) Data[], (배열 데이터 수) int n
Output : (정렬 후 데이터 배열) Data[]
BubbleSort(int Data[], int n) {
for (i = 0; i < n-1; i++) // (입력 개수 - 1)까지 반복
sorted = TRUE;
for (j = 0; j < n - (i+1); j++) // (대상 개수 - 1)까지 반복
if (Data[j] > Data[j+1]) // 순서 맞지 않으면 (비교)
Data[j] ↔ Data[j+1]; // 자리바꿈 (교환)
sorted = FALSE; // 교환 발생했으므로, 플래그 설정
if (sorted == TRUE) return; // 입력이 이미 정렬 상태이면, 바로 종료
}