거품 정렬(Bubble Sort)
뒤에서 부터 앞으로 정렬을 해나가는 방식으로 첫번째 값부터 시작해서 다음 값들과 차례로 비교하면서 가장 큰 값 부터 맨 뒤에 쌓아나감
특징
거품 정렬은 점점 큰 값들을 뒤에서 부터 앞으로 하나씩 쌓여 나가게 때문에 후반으로 갈수록 정렬 범위가 하나씩 줄어들게 됨
제일 작은 값을 찾아서 맨 앞에 위치시키는 선택 정렬과 비교했을 때 정반대의 정렬 방향을 가짐
복잡도
- 공간 복잡도 O(1)
거품 정렬은 별도의 추가 공간을 사용하지 않고 주어진 배열이 차지하고 있는 공간 내에서 값들의 위치만 바꾸기 때문에 O(1)의 공간 복잡도 - 시간 복잡도
루프문을 통해 맨 뒤부터 맨 앞까지 모든 인덱스에 접근해야 하기 때문에 기본적으로 O(N)을 시간을 소모하며, 하나의 루프에서 인접한 값들 간 대소 비교 및 자리 교대를 위해서 O(N)을 시간이 필요하므로 총 O(N^2)의 시간 복잡도
구현
- 선택 정렬과 마찬가지로 두 개의 반복문이 필요
- 내부 반복문에서는 첫번째 값부터 이전 패스에서 뒤로 보내놓은 값이 있는 위치 전까지 앞뒤 값을 계속해서 비교해나가면서 앞의 값이 뒤의 값보다 클 경우 자리 교대(swap)
- 외부 반복문에서는 뒤에서 부터 앞으로 정렬 범위를 n-1부터 1까지 줄여나갑니다.
public class Bubble {
public static void sort(int[] arr) {
for (int i = arr.length - 1; i > 0; i--) {
for (int j = 0; j <= i; j++) {
if (arr[j] > arr[j + 1])
swap(arr, j, j + 1);
}
}
}
private static void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}최적화
이전 패스에서 앞뒤 자리 비교(swap)이 한 번도 일어나지 않았다면 정렬되지 않는 값이 하나도 없었다고 간주할 수 있습니다. 따라서 이럴 경우, 이후 패스를 수행하지 않아도 됩니다.
Initial: [1, 2, 3, 5, 4]
Pass 1: [1, 2, 3, 4, 5] => Swap 있었음
Pass 2: [1, 2, 3, 4, 5] => Swap 없었음
*
=> 이전 패스에서 swap이 한 번도 없었으니 종료
public class Bubble {
public static void sort(int[] arr) {
for (int i = arr.length - 1; i > 0; i--) {
boolean swapped = false;
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
swapped = true;
}
}
if (!swapped) break;
}
}
private static void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}추가 최적화
이전 패스에서 앞뒤 자리 비교(swap)가 있었는지 여부를 체크하는 대신 마지막으로 앞뒤 자리 비교가 있었던 index를 기억해두면 다음 패스에서는 그 자리 전까지만 정렬하면 되므로 한 칸씩 정렬 범위를 줄여나가는 대신 한번에 여러 칸씩 정렬 범위를 줄여나갈 수 있음
public class Bubble {
public static void sort(int[] arr) {
int end = arr.length - 1;
while (end > 0) {
int last_swap = 0;
for (int i = 0; i < end; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
last_swap = i;
}
}
end = last_swap;
}
}
private static void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}