버블 정렬(Bubble Sort)은 비교 기반의 단순한 정렬 알고리즘으로, 인접한 두 원소를 비교하여 필요에 따라 자리를 교환하는 방식으로 정렬을 수행합니다. 버블 정렬은 배열이 거의 정렬되어 있을 때 효율적일 수 있지만, 일반적으로 성능이 좋지 않아 큰 데이터셋에서는 잘 사용되지 않습니다.
버블 정렬의 동작 원리
- 배열의 처음부터 시작: * 첫 번째 원소와 두 번째 원소를 비교하여, 첫 번째 원소가 더 크면 두 원소의 위치를 교환합니다. * 두 번째 원소와 세 번째 원소를 비교하여, 두 번째 원소가 더 크면 두 원소의 위치를 교환합니다. * 이 과정을 배열의 끝까지 반복합니다.
- 반복: * 위의 과정을 배열의 끝까지 반복하면 가장 큰 원소가 배열의 마지막으로 이동합니다. * 이를 배열의 크기만큼 반복하면 전체 배열이 정렬됩니다.
예제
배열 [5, 2, 9, 1, 5, 6]을 버블 정렬하는 과정을 단계별로 설명합니다.
- 첫 번째 패스: * [5, 2, 9, 1, 5, 6] * 5와 2를 비교: [2, 5, 9, 1, 5, 6] * 5와 9를 비교: [2, 5, 9, 1, 5, 6] * 9와 1을 비교: [2, 5, 1, 9, 5, 6] * 9와 5를 비교: [2, 5, 1, 5, 9, 6] * 9와 6을 비교: [2, 5, 1, 5, 6, 9]
- 두 번째 패스: * [2, 5, 1, 5, 6, 9] * 2와 5를 비교: [2, 5, 1, 5, 6, 9] * 5와 1을 비교: [2, 1, 5, 5, 6, 9] * 5와 5를 비교: [2, 1, 5, 5, 6, 9] * 5와 6을 비교: [2, 1, 5, 5, 6, 9] * (마지막 원소는 이미 정렬된 상태)
- 세 번째 패스: * [2, 1, 5, 5, 6, 9] * 2와 1을 비교: [1, 2, 5, 5, 6, 9] * 2와 5를 비교: [1, 2, 5, 5, 6, 9] * 5와 5를 비교: [1, 2, 5, 5, 6, 9] * (마지막 두 원소는 이미 정렬된 상태)
- 네 번째 패스: * [1, 2, 5, 5, 6, 9] * 1과 2를 비교: [1, 2, 5, 5, 6, 9] * 2와 5를 비교: [1, 2, 5, 5, 6, 9] * (마지막 세 원소는 이미 정렬된 상태)
- 다섯 번째 패스: * [1, 2, 5, 5, 6, 9] * 1과 2를 비교: [1, 2, 5, 5, 6, 9] * (마지막 네 원소는 이미 정렬된 상태)
버블 정렬의 시간 복잡도
- 최선의 경우: O(n) (배열이 이미 정렬되어 있는 경우)
- 평균적인 경우: O(n^2)
- 최악의 경우: O(n^2) (배열이 역순으로 정렬되어 있는 경우)
버블 정렬의 장단점
- 장점:
- 구현이 매우 간단합니다.
- 적은 양의 데이터에 대해서는 효율적입니다.
- 대부분의 원소가 정렬된 경우 효율적일 수 있습니다.
- 단점:
- 시간 복잡도가 O(n^2)로, 큰 데이터셋에 대해 비효율적입니다.
- 최적화된 다른 정렬 알고리즘에 비해 성능이 좋지 않습니다.
import java.util.Arrays;
public class BubbleSort {
// 버블 정렬 메서드
public void sort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// 각 패스마다 마지막 i개의 요소는 이미 정렬된 상태입니다.
for (int j = 0; j < n - 1 - i; j++) {
// 인접한 두 요소를 비교하여 교환합니다.
if (arr[j] > arr[j + 1]) {
// 요소를 교환합니다.
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 메인 메서드
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 5, 6};
System.out.println("정렬 전 배열:");
System.out.println(Arrays.toString(arr));
// 버블 정렬 수행
new BubbleSort().sort(arr);
System.out.println("정렬 후 배열:");
System.out.println(Arrays.toString(arr));
}
}