Bubble Sort
개요
버블 정렬은 정렬 알고리즘 중 하나로, 인접한 두 원소를 비교하고 필요시 교환하여 배열을 정렬하는 방법이다. 이 알고리즘은 간단하고 직관적이지만, 큰 데이터셋에 대해서는 비효율적이다.
버블 정렬의 동작 원리
- 첫 번째 패스: 배열의 첫 번째 원소와 두 번째 원소를 비교하여, 순서가 맞지 않으면 두 원소를 교환한다. 이 과정을 배열의 끝까지 반복하여 가장 큰 원소가 맨 뒤로 이동한다.
- 두 번째 패스: 첫 번째 패스에서 가장 큰 원소가 정렬되었기 때문에, 마지막 원소를 제외하고 나머지 원소들을 비교하여 동일한 과정을 반복한다.
- 반복: 이 과정을 배열이 완전히 정렬될 때까지 반복한다. 매 패스마다 정렬된 원소는 비교에서 제외된다.
예제 코드
기본 버블 정렬
public class BubbleSort {
public static void sort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) { // n-1 회전
for (int j = 0; j < n - i - 1; j++) { // 비교할 인덱스 선택
if (arr[j] > arr[j + 1]) { // 두 원소 비교
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.print((i + 1) + "단계 : ");
print(arr);
}
}
private static void print(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {6, 2, 4, 3, 7, 1, 9};
sort(arr);
}
}
최적화된 버블 정렬
기본 버블 정렬은 이미 정렬된 배열에 대해서도 불필요한 반복을 한다. 이를 개선하기 위해 배열이 이미 정렬된 경우 루프를 일찍 종료하는 최적화된 버블 정렬을 구현할 수 있다.
public class OptimizedBubbleSort {
public static void sort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break; // 교환이 없으면 정렬 완료
System.out.print((i + 1) + "단계 : ");
print(arr);
}
}
private static void print(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
sort(arr);
}
}
단계별 설명
예제 배열: [6, 2, 4, 3, 7, 1, 9]
-
1단계:
6과 2 비교 -> 교환
6과 4 비교 -> 교환
6과 3 비교 -> 교환
6과 7 비교 -> 교환 안함
7과 1 비교 -> 교환
7과 9 비교 -> 교환 안함
결과: 2, 4, 3, 6, 1, 7, 9 -
2단계:
2와 4 비교 -> 교환 안함
4와 3 비교 -> 교환
4와 6 비교 -> 교환 안함
6과 1 비교 -> 교환
6과 7 비교 -> 교환 안함
결과: 2, 3, 4, 1, 6, 7, 9 -
3단계:
2와 3 비교 -> 교환 안함
3와 4 비교 -> 교환 안함
4와 1 비교 -> 교환
4와 6 비교 -> 교환 안함
결과: 2, 3, 1, 4, 6, 7, 9 -
4단계:
2와 3 비교 -> 교환 안함
3과 1 비교 -> 교환
3과 4 비교 -> 교환 안함
결과: 2, 1, 3, 4, 6, 7, 9 -
5단계:
2와 1 비교 -> 교환
2와 3 비교 -> 교환 안함
결과: 1, 2, 3, 4, 6, 7, 9 -
6단계:
1과 2 비교 -> 교환 안함
결과: 1, 2, 3, 4, 6, 7, 9 -
7단계:
이미 정렬 완료
결과: 1, 2, 3, 4, 6, 7, 9
시간 복잡도
버블 정렬의 시간 복잡도는 다음과 같다
- 최악의 경우: O(N^2) - 모든 원소가 역순으로 정렬된 경우.
- 최선의 경우: O(N) - 배열이 이미 정렬된 경우 (최적화된 버블 정렬의 경우).
- 평균의 경우: O(N^2) - 일반적인 경우.
공간 복잡도
버블 정렬은 주어진 배열 내에서 정렬을 수행하므로 추가적인 메모리 공간이 필요하지 않다. 따라서 공간 복잡도는 O(1)이다.
장점
- 구현이 간단하고 소스코드가 직관적이다.
- 이미 정렬된 데이터를 정렬할 때, 최적화된 버블 정렬은 빠르게 완료될 수 있다.
- 정렬하고자 하는 배열 안에서 정렬하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.
- 안정 정렬로, 동일한 값의 원소 순서가 유지된다.
단점
- 시간 복잡도가 O(N^2)로, 큰 데이터셋에 대해 비효율적이다.
- 다른 효율적인 정렬 알고리즘에 비해 느리다.
- 교환 횟수가 많아질 수 있어, 성능에 영향을 미친다.
So...
버블 정렬은 간단하고 직관적인 정렬 알고리즘으로, 인접한 두 원소를 비교하여 교환하는 방식을 사용한다. 구현이 쉬우며, 작은 데이터셋에 적합하지만, 큰 데이터셋에 대해서는 비효율적이다. 버블 정렬을 통해 기본적인 정렬 개념을 이해할 수 있으며, 다른 정렬 알고리즘과의 차이점을 파악하는 데 도움이 된다.
