인접한 두 개의 원소를 비교하며 자리를 계속 교환하며 정렬하는 알고리즘
정렬 과정
- 첫 번째 원소와 두 번째 원소, 두 번째 원소와 세 번째 원소, ... , (마지막-1) 번째 원소와 마지막 원소를 비교하며 조건에 맞게 자리를 교환한다.
- 정렬을 1회전 수행한 후에는 제일 큰 원소가 마지막 위치로 이동한다. 2회전 후에는 두 번째로 큰 원소가 (마지막-1) 위치로 이동한다. 즉, 각 회전이 진행될 때마다 원소가 하나씩 정렬에서 제외된다.
소스 코드
void BubbleSort() {
int[] nums = {1000, 400, 12, -59, 328, 121, -3};
// loop 1
for(int i = 0; i < nums.length; i++) {
// loop2
for(int j = 0; j < nums.length-(i+1); j++) {
if(nums[j] > nums[j+1]) {
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
System.out.println(Arrays.toString(nums));
}loop 1: 정렬에서 제외될 원소의 갯수를 의미한다.
loop 2: j 번째 원소와 j+1 번째 원소를 비교한 후 자리를 바꿔준다. i의 값이 증가할 때마다 순회할 원소의 갯수가 하나씩 감소한다.
시간 복잡도
각 회전에서의 비교 횟수를 더해보면 위와 같으므로, 모든 경우에서 O(N^2) 이다.
공간 복잡도
단 하나의 배열에서만 진행되므로 O(n) 이다.
장점
- 구현이 매우 간단하고, 코드가 직관적이다.
- 제자리 정렬(in-place sorting) 이므로 다른 메모리 공간을 필요로 하지 않는다.
- 안정 정렬(stable sort) 이다.
단점
- 시간 복잡도가 모든 경우에서 O(N^2) 이므로 매우 비효율적이다.
- 원소가 자리를 찾아가는 과정에서 교환 연산이 많이 발생한다.
[참고]
