1. 알고리즘 개념
- 인접한 2개의 레코드를 비교하며 정렬
- 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환
- 1회전이 돌때 마다 정렬이 완료된 레코드가 가장 오른쪽에 1개씩 추가됨

2. 코드 - Java
<java />
// buble sort
for(int i = N-1; i >=0 ; i--) {
int chage = 0;
for(int j=0; j<i; j++) {
if(arr[j]> arr[j+1]) {
chage++;
int tem = arr[j];
arr[j] = arr[j+1];
arr[j+1]= tem;
}
}
if(chage == 0) break;
}
3. 시간 복잡도 분석
3.1. 비교 횟수
- (n-1) + (n-2) .. 2 + 1 = (n * (n+1)) / 2
- 시간 복잡도: O(n^2)
- 최선, 평균, 최악 모두 같다.
3.2. 이동 횟수
- 최악의 경우, 인접한 레코드가 계속 교환되기 때문에 마찬가지로 O(n^2)
- 이때 교환은 3번의 이동을 포함하기 때문에 실제 횟수는 3을 곱한 값이다.
-
- 시간 복잡도: O(n^2)이동 횟수
최악 평균 최선 O(n^2) O(n^2)/2 0
총 시간 복잡도 : O(n^2)
4. 단점
- 특정 요소가 최종 정렬 위치에 있는 경우에도 교환이 일어날 수 있다.
- 하나의 요소가 가장 오른쪽에서 왼쪽으로 이동하기 위해서는 모든 요소와 비교, 교환 작업이 일어난다.
- 일반적으로 자료의 교환작업이 이동 작업보다 복잡하기 때문에 버블정렬을 거의 쓰이지 않는다.
'CS > 알고리즘' 카테고리의 다른 글
Java BFS와 DFS 구현 (0) | 2023.09.17 |
---|---|
합병 정렬 (Merge Sort) - Java (0) | 2023.08.19 |
퀵 정렬 (Quick Sort) - Java (0) | 2023.08.17 |
삽입 정렬 - Java (0) | 2023.08.16 |
선택 정렬 - Java (0) | 2023.08.14 |