버블정렬(Bubble Sort)이란?
개념
버블 정렬은 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이다.
과정
(굵은 글자는 인접한 두 개의 비교를 뜻하고, 빨간색은 자리 교환이 이루어진 것)
{16, 2, 31, 14, 5} 리스트가 있을 때 버블 정렬을 시작하면
1회전
{2, 16, 31, 14, 5} ⇒ (16, 2) 비교하여 16이 더 크므로 자리 교환
{2, 16, 31, 14, 5} ⇒ (16, 31) 비교하여 31이 더 크므로 자리 교환 안함
{2, 16, 14, 31, 5} ⇒ (31, 14) 비교하여 31이 더 크므로 자리 교환
{2, 16, 14, 5, 31} ⇒ (31, 5) 비교하여 31이 더 크므로 자리 교환
1회전을 끝내면 가장 큰 자료인 31이 맨 뒤로 이동하게 된다.
2회전
1회전 때 나온 맨 뒷자리를 제외한 원소들로 반복하게 된다.
{2, 16, 14, 5, 31} ⇒ (2, 16) 비교 후 자리 교환 안함
{2, 14, 16, 5, 31} ⇒ (16, 14) 비교 후 자리 교환
{2, 14, 5, 16, 31} ⇒ (16, 5) 비교 후 자리 교환
2회전을 끝내면 31을 제외하고 가장 큰 자료인 16이 맨 뒤로 가게 된다.
3회전
{2, 14, 5, 16, 31} ⇒ (2, 14) 비교 후 자리 교환 안함
{2, 5, 14, 16, 31} ⇒ (14, 5) 비교 후 자리 교환
2회전에서 가장 큰 값인 16을 제외하고 가장 큰 자료인 14가 맨 뒤로 가게 된다.
4회전
{2, 5, 14, 16, 31} ⇒ (2, 5) 비교 후 자리 교환 안함
정렬이 끝남
구현(C++)
#include <stdio.h>
int main()
{
int n, i, j, a[5], temp;
scanf("%d", &n); // 데이터의 개수 n을 정한다.
for (i = 0; i < n; i++) // n개만큼 데이터 값을 받는다.
{
scanf("%d", &a[i]);
}
// 버블 정렬 시작
for (i = 0; i < n - 1; i++) // 마지막 값은 자동 정렬되므로 n-1번까지만 반복한다.
{
for (j = 0; j < n - i - 1; j++) // i번 돌때마다 마지막 값에는 큰 값이 들어오므로 끝까지 비교할 필요가 없다. 따라서 n-i-1번까지만 비교한다.
{
if (a[j] > a[j + 1]) // 인접한 2개를 비교했을 때 처음 위치값이 크다면 자리 교환
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
// 버블 정렬 끝났으므로 출력한다.
for (i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
return 0;
}이렇게 버블 정렬이 동작하게 된다.
버블 정렬을 돌리면서 생각났는데 정렬이 이미 끝났어도 현재 코드에서는 계속 반복하여 비교하게 된다.
만약 위 그림처럼 {1, 2, 3, 4, 5}가 들어와서 버블 정렬을 시작하면 1회전에서 저렇게 의미없이 비교를 하게된다.
그리고 이 과정을 4회전까지 하게 된다.
따라서 정렬이 끝났는데도 계속 반복하는 것을 중단시키려면 다음 코드에서 check를 추가해보자.
#include <stdio.h>
int main()
{
int n, i, j, a[5], temp, check;
scanf("%d", &n); // 데이터의 개수 n을 정한다.
for (i = 0; i < n; i++) // n개만큼 데이터 값을 받는다.
{
scanf("%d", &a[i]);
}
// 버블 정렬 시작
for (i = 0; i < n - 1; i++) // 마지막 값은 자동 정렬되므로 n-1번까지만 반복한다.
{
check = 0; // 1번 돌 때마다 0으로 초기화한다.
for (j = 0; j < n - i - 1; j++) // i번 돌때마다 마지막 값에는 큰 값이 들어오므로 끝까지 비교할 필요가 없다. 따라서 n-i-1번까지만 비교한다.
{
if (a[j] > a[j + 1]) // 인접한 2개를 비교했을 때 처음 위치값이 크다면 자리 교환
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
if (check == 0) // 모든 자리의 값을 비교했는데 자리 교환이 이루어지지 않았다면 이미 정렬이 끝난 상태이므로 반복을 그만한다.
break;
}
// 버블 정렬 끝났으므로 출력한다.
for (i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
return 0;
}위 코드처럼 1회전 할 때마다 check를 0으로 초기화해주고, 내부 for문일 때 전부 비교를 하는데 자리교환이 이루어지지 않으면 정렬이 끝났다고 판단되어 반복을 끝내게 된다.
시간 복잡도
최악일 때는 이것 또한 선택 정렬(Selection Sort)이랑 똑같은 시간 복잡도인 O(n^2)이다.
하지만 중간에 필요없는 반복을 끝내는 최선(최적)일 때를 보면 1번만에 끝나기도 하므로 이 때는 O(n)이 된다.
정렬 비교
교환 작업이 많이 이루어져서 이것 보다는 선택 정렬을 사용하는 것이 성능적으로 더 우수하다.