1. 버블 정렬(Bubble Sort)이란?
ㆍ두 인접한 데이터의 크기를 비교해 정렬하는 방법(오름차순, 내림차순)
ㆍ인접한 데이터 간의 swap 연산으로 정렬
ㆍ교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라 함
2. 정렬 과정
ㆍ인접한 데이터 값을 비교
ㆍ조건에 부합하면 swap 연산을 수행
ㆍ범위가 끝날 때까지 반복
3. 시간복잡도
ㆍ O(n²)
4. 코드 예제
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
// 배열을 선언하고 원소를 5개로 초기화
int[] arr = { 42, 32, 24, 68, 15 };
System.out.println("버블 정렬 전: " + Arrays.toString(arr));
// 반복문을 통해서 버블 정렬을 실시
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
// i번째 원소와, j번째 원소를 비교한다.
// 이 때, j는 항상 i 바로 옆에 있는 원소를 가리킬 수 있도록 i+1로 초기화한다.
if (arr[i] > arr[j]) {
// swap 하기 위해 값을 보관할 수 있는 tmp를 생성한다.
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
System.out.println("버블 정렬(오름차순) 후: " + Arrays.toString(arr));
}
}
5. 버블 정렬의 장ㆍ단점
ㆍ장점
- 구현이 매우 간단하다.
ㆍ단점
- 순서에 맞지 않은 요소를 인접한 요소와 교환한다.
- 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
- 일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.
'알고리즘 > 이론' 카테고리의 다른 글
[JAVA]검색(2) - 이진 검색(Binary Search) (0) | 2023.01.12 |
---|---|
[JAVA] 검색(1) - 순차 검색(선형 검색, Sequential Search) (0) | 2023.01.11 |
[JAVA]정렬(2) - 선택 정렬(Selection Sort) (0) | 2023.01.10 |
댓글