버블 정렬의 동작 원리
버블 정렬 (Bubble Sort) 은 배열 내부에서 인접한 두 데이터를 비교하여 순서가 틀린 경우 위치를 교환하는 과정을 반복하는 정렬 기법입니다. 이 과정에서较大的인 값이 점차 배열의 뒤쪽으로 이동하게 되는데, 마치 물속에서 거품이 위로 올라오는 모습과 유사하여 이러한 이름이 붙었습니다.
알고리즘은 배열의 처음부터 끝까지 반복적으로 순회하며, 매 통과 (pass) 마다 정렬되지 않은 부분 중 가장 큰 값을 올바른 위치로 이동시킵니다. 더 이상 교환할 요소가 남지 않을 때까지 이 과정을 지속하면 배열은 정렬된 상태가 됩니다.
C 언어를 통한 기본 구현
버블 정렬을 C 언어로 구현할 때는 중첩 반복문을 사용하여 요소를 비교하고 교환합니다. 교환 과정에서는 포인터를 활용한 함수 호출 또는 임시 변수를 이용한 직접 교환 방식을 사용할 수 있습니다. 아래 예시는 임시 변수를 사용하여 인라인으로 교환 로직을 처리한版本입니다.
void performBubbleSort(int* dataSet, int size) {
int outerIdx, innerIdx;
int temporary;
// 외부 루프: 전체 pass 횟수 제어
for (outerIdx = 0; outerIdx < size - 1; outerIdx++) {
// 내부 루프: 인접 요소 비교 및 교환
// 매 pass 때마다 마지막 요소는 정렬되므로 비교 범위를 줄임
for (innerIdx = 0; innerIdx < size - outerIdx - 1; innerIdx++) {
// 오름차순 정렬 기준: 앞 요소가 뒤 요소보다 크면 교환
if (dataSet[innerIdx] > dataSet[innerIdx + 1]) {
temporary = dataSet[innerIdx];
dataSet[innerIdx] = dataSet[innerIdx + 1];
dataSet[innerIdx + 1] = temporary;
}
}
}
}위 코드에서 외부 루프는 정렬 라운드를 관리하며, 내부 루프는 실제 비교 연산을 수행합니다. 내부 루프의 범위가 size - outerIdx - 1로 설정된 이유는, 이미 지난 라운드에서 배열 끝부분으로 최대값들이 이동되었기 때문에 중복 비교를 방지하기 위함입니다.
알고리즘 효율성 개선
기본 구현 방식은 배열이 이미 정렬되어 있더라도 모든 비교 과정을完行합니다. 이는 불필요한 연산 낭비로 이어질 수 있습니다. 이를 개선하기 위해 특정 라운드에서 요소 교환이 전혀 발생하지 않았다면, 이미 정렬이 완료된 상태로 간주하여 루프를 조기 종료하는 최적화가 가능합니다.
교환 발생 여부를 기록하는 플래그 변수를 도입하여 불필요한 순회를 차단할 수 있습니다.
void performBubbleSortOptimized(int* dataSet, int size) {
int outerIdx, innerIdx;
int temporary;
int isSwapped;
for (outerIdx = 0; outerIdx < size - 1; outerIdx++) {
// 해당 라운드에서 교환 발생 여부를 초기화 (0: 없음, 1: 있음)
isSwapped = 0;
for (innerIdx = 0; innerIdx < size - outerIdx - 1; innerIdx++) {
if (dataSet[innerIdx] > dataSet[innerIdx + 1]) {
temporary = dataSet[innerIdx];
dataSet[innerIdx] = dataSet[innerIdx + 1];
dataSet[innerIdx + 1] = temporary;
// 교환이 발생했으므로 플래그 설정
isSwapped = 1;
}
}
// 한 바퀴를 돌았는데 교환이 없었다면 정렬 완료
if (isSwapped == 0) {
break;
}
}
}최적화된 코드에서는 내부 루프가 완료된 시점에 isSwapped 값을 확인합니다. 만약 값이 0이라면 추가적인 비교 연산 없이 함수를 종료하여 성능을 향상시킬 수 있습니다.
알고리즘 복잡도 및 특성 분석
- 시간 복잡도:
- 최악의 경우 (역순 정렬): 모든 요소 쌍을 비교해야 하므로 O(n²) 의 연산량이 발생합니다.
- 최선의 경우 (이미 정렬됨): 최적화된 알고리즘 적용 시 한 번의 순회만으로 종료되므로 O(n) 의 성능을 보입니다.
- 평균 경우: 일반적으로 O(n²) 를 가집니다.
- 공간 복잡도: 추가적인 배열 할당 없이 기존 배열 내에서 교환만 수행하므로 O(1) 의 상수 공간만 필요합니다.
- 안정성 (Stability): 동일한 값에 대해 교환을 수행하지 않으므로 (조건문에서 > 만 사용), 정렬 전후의 상대적 순서가 유지되는 안정 정렬 (Stable Sort) 입니다.