[java] 버블 정렬 알고리즘
개요
버블 정렬은 인접한 두 개의 요소를 비교하여 정렬하는 알고리즘 중 하나입니다. 이 알고리즘은 단순하지만 성능이 좋지 않아 큰 리스트에서는 사용하기 어렵습니다.
동작 원리
버블 정렬은 리스트를 순회하면서 인접한 두 요소를 비교하고, 순서가 잘못되어 있으면 교환하는 과정을 반복합니다. 모든 요소의 비교와 교환을 마친 후에는 정렬이 완료됩니다.
코드 예시
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
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;
}
}
}
}
public static void main(String[] args) {
int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
bubbleSort(arr);
System.out.println("정렬된 배열: ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
시간 복잡도
버블 정렬의 시간 복잡도는 O(n^2)입니다. 외부 루프가 n-1번, 내부 루프가 최대 n-1, n-2, …, 1번 수행되기 때문에 모두 곱해서 n(n-1)/2번 수행됩니다.