C 프로그래밍 언어에서 버블 정렬(bubble sort)은 가장 간단한 정렬 기법으로, '교환 정렬(exchange sort)'이라고도 불립니다. 인접한 두 요소를 반복적으로 비교하며 큰 값을 뒤로 밀어내는 방식으로, 마치 물속의 거품이 위로 떠오르는 모습과 비슷하다고 하여 이런 이름이 붙었습니다.
버블 정렬의 동작 원리
목록의 첫 번째 요소를 나머지 요소들과 차례대로 비교하고, 순서가 맞지 않으면 서로 교환(swap)합니다.
모든 요소가 정렬될 때까지 이 과정을 반복합니다.
알고리즘
다음은 버블 정렬 기법을 사용하여 주어진 숫자 목록을 오름차순으로 정렬하는 알고리즘입니다.
1단계 – 시작
2단계 – 목록(배열) list와 요소 개수 num 선언
3단계 – readlist(list, num) 호출
4단계 – printlist(list, num) 호출
5단계 – bub_sort(list, num) 호출
6단계 – printlist(list, num) 호출
7단계 – 종료
readlist(list, num)
1. for j = 0 to num 2. read list[j].
printlist(list, num)
1. for j = 0 to num 2. write list[j].
bub_sort(list, num)
1. for i = 0 to num 2. for j = 0 to (num – i) 3. if( list[j] > list[j+1]) 4. swapList( address of list[j], address of list[j+1])
swapList(address of list[j], address of list[j+1])
1. temp = value at list[j] 2. value at list[j] = value at list[j+1] 3. value at list[j+1] = temp
예제 코드
다음은 버블 정렬 기법을 사용하여 주어진 숫자 목록을 오름차순으로 정렬하는 C 프로그램입니다.
#include <stdio.h>
#define MAX 10
void swapList(int *m,int *n){
int temp;
temp = *m;
*m = *n;
*n = temp;
}
/* Function for Bubble Sort */
void bub_sort(int list[], int n){
int i,j;
for(i=0;i<(n-1);i++)
for(j=0;j<(n-(i+1));j++)
if(list[j] > list[j+1])
swapList(&list[j],&list[j+1]);
}
void readlist(int list[],int n){
int j;
printf("\nEnter the elements: \n");
for(j=0;j<n;j++)
scanf("%d",&list[j]);
}
/* Showing the contents of the list */
void printlist(int list[],int n){
int j;
for(j=0;j<n;j++)
printf("%d\t",list[j]);
}
void main(){
int list[MAX], num;
printf(" Enter the number of elements \n");
scanf("%d",&num);
readlist(list,num);
printf("\n\nElements in the list before sorting are:\n");
printlist(list,num);
bub_sort(list,num);
printf("\n\nElements in the list after sorting are:\n");
printlist(list,num);
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
Enter the number of elements 10 Enter the elements: 11 23 45 1 3 6 35 69 10 22 Elements in the list before sorting are: 11 23 45 1 3 6 35 69 10 22 Elements in the list after sorting are: 1 3 6 10 11 22 23 35 45 69
버블 정렬의 시간 복잡도
버블 정렬은 인접한 두 요소를 계속 비교하고 교환하기 때문에 최악의 경우와 평균적인 경우의 시간 복잡도는 O(n²)입니다. 반면 이미 정렬되어 있는 목록이 입력되는 최선의 경우에는 불필요한 교환이 줄어들어 성능이 개선될 수 있습니다. 구현이 매우 단순해서 학습용으로 적합하지만, 데이터가 많아지면 퀵 정렬이나 병합 정렬처럼 더 효율적인 알고리즘을 사용하는 것이 좋습니다.