[JAVA] 정렬(1) - 버블 정렬(Bubble Sort)

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)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.