버블 정렬은 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘입니다.
버블 정렬 알아보기
배열을 통해 버블 정렬을 알아봅니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| value | 6 | 4 | 3 | 7 | 1 | 9 | 8 |
끝에 있는 두 요소부터 시작합니다. 배열이 오름차순이라면 왼쪽 값이 오른쪽 값보다 작아야 합니다. 따라서 9와 8을 교환한 배열은 다음과 같습니다:
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| value | 6 | 4 | 3 | 7 | 1 | 8 | 9 |
그 다음 1과 8을 비교합니다. 1은 8보다 작으므로 교환하지 않습니다. 이 과정을 요소수가 n개인 배열에서 n-1번 비교, 교환 하고 나면 가장 작은 요소가 맨 처음으로 이동하며 이 과정(비교, 교환)을 패스라고 합니다.
| 시작 | 6 | 4 | 3 | 7 | 1 | 9 | 8 |
|---|---|---|---|---|---|---|---|
| 2차 | 6 | 4 | 3 | 7 | 1 | 8 | 9 |
| 3차 | 6 | 4 | 3 | 7 | 1 | 8 | 9 |
| 4차 | 6 | 4 | 3 | 1 | 7 | 8 | 9 |
| 5차 | 6 | 4 | 1 | 3 | 7 | 8 | 9 |
| 6차 | 6 | 1 | 4 | 3 | 7 | 8 | 9 |
| 종료 | 1 | 6 | 4 | 3 | 7 | 8 | 9 |
이어서 두 번째 이후 요소를 비교, 교환하는 패스를 수행합니다.
| 시작 | 6 | 4 | 3 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|
| 2차 | 6 | 4 | 3 | 7 | 8 | 9 | |
| 3차 | 6 | 4 | 3 | 7 | 8 | 9 | |
| 4차 | 6 | 4 | 3 | 7 | 8 | 9 | |
| 5차 | 6 | 3 | 4 | 7 | 8 | 9 | |
| 종료 | 3 | 6 | 3 | 7 | 8 | 9 |
이 패스를 수행하면 두 번째 작은 수인 3은 두 번째 자리로 이동합니다.
다음은 위 내용을 바탕으로 작성한 버블 정렬 프로그램입니다:
//--- 버블 정렬 ---//
static void bubbleSort(int[] a, int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = n - 1; j > i; j--) {
if (a[j - 1] > a[j]) { //왼쪽의 값이 더 크다면
int t = a[j - 1]; //왼쪽 값을 임시값에 대입한 뒤
a[j - 1] = a[j]; //오른쪽 값을 왼쪽 값에 대입하고
a[j] = t; //임시값을 오른쪽 값에 대입한다
}
}
}
}서로 이웃한 요소만 교환하므로 이 정렬 알고리즘은 안정적이라고 할 수 있습니다. 첫 번째 패스의 비교횟수는 n-1회, 두번째는 n-2회 이므로 비교 횟수는 회 입니다.
교환 횟수의 평균값은 비교 횟수의 절반인 회 입니다.
값의 이동 횟수의 평균값은 교환을 위해 3번 움직이므로 회 입니다.
알고리즘 개선하기1
다음은 위의 배열을 2번 더 정렬한 상태를 보여줍니다.
| 시작 | 6 | 7 | 8 | 9 | |||
|---|---|---|---|---|---|---|---|
| 2차 | 6 | 7 | 8 | 9 | |||
| 3차 | 6 | 7 | 8 | 9 | |||
| 종료 | 6 | 7 | 8 | 9 |
배열이 정렬을 이미 마친 상태이면 그 이후의 패스는 요소를 교환하지 않으므로 교환 횟수가 0이면 정렬 작업을 멈춥니다.
다음은 버블 정렬 프로그램을 개선한 내용입니다:
//--- 버블 정렬 ---//
static void bubbleSort(int[] a, int n) {
for (int i = 0; i < n - 1; i++) {
int exchg = 0;
for (int j = n - 1; j > i; j--) {
if (a[j - 1] > a[j]) { //왼쪽의 값이 더 크다면
int t = a[j - 1]; //왼쪽 값을 임시값에 대입한 뒤
a[j - 1] = a[j]; //오른쪽 값을 왼쪽 값에 대입하고
a[j] = t; //임시값을 오른쪽 값에 대입한다
exchg++; //정렬횟수를 증가시킨다
}
}
if(exchg == 0) break; //교환이력이 없으면 종료한다.
}
}알고리즘 개선하기2
다음은 배열 {1,3,9,4,7,8,6}을 버블 정렬을 1회만 합니다.
| 시작 | 1 | 3 | 9 | 4 | 7 | 8 | 6 |
|---|---|---|---|---|---|---|---|
| 2차 | 1 | 3 | 9 | 4 | 7 | 6 | 8 |
| 3차 | 1 | 3 | 9 | 4 | 6 | 7 | 8 |
| 4차 | 1 | 3 | 4 | 9 | 6 | 7 | 6 |
| 5차 | 1 | 3 | 4 | 9 | 6 | 7 | 6 |
| 6차 | 1 | 3 | 4 | 9 | 6 | 7 | 6 |
| 종료 | 1 | 3 | 4 | 9 | 6 | 7 | 6 |
교환을 마치고 난 뒤 살펴보면 5차 이후로는 정렬을 실행하지 않습니다. 이는 마지막 어떤 시점 이후로 교환을 하지 않는다면 그보다 앞쪽요소는 이미 교환을 마친 상태인 것이므로 두번째 패스는 n-1인 6개 요소를 비교하는 것이 아닌 4개의 요소만 비교하면 됩니다.
다음은 버블 정렬 프로그램을 개선한 내용입니다:
//--- 버블 정렬(버전 3: 스캔 범위를 한정)---//
static void bubbleSort(int[] a, int n) {
int k = 0; // a[k]보다 앞쪽은 정렬을 마침
while (k < n - 1) {
int last = n - 1; // 마지막으로 교환한 위치
for (int j = n - 1; j > k; j--)
if (a[j - 1] > a[j]) {
int t = a[j - 1]; //왼쪽 값을 임시값에 대입한 뒤
a[j - 1] = a[j]; //오른쪽 값을 왼쪽 값에 대입하고
a[j] = t; //임시값을 오른쪽 값에 대입한다
last = j; //마지막 교환위치를 대입한다.
}
k = last;
}
}