[정렬]0.1 버블 정렬

여러 가지 형태의 정렬 방식을 살펴보고 그 동작의 차이점을 고민해보자. 사실 어떤 정렬 알고리즘이 빠른지는 이미 다 나와있기 때문에 쓸데없이 버블 정렬 같은것을 살펴볼 필요가 있을가 싶기도 하겠지만 알고리즘을 공부하면서 아이디어의 정리 차원이라고 생각하면 좋겠다.

 

여기서 소개하는 모든 정렬들은 기본적으로 오름 차순 정렬을 사용한다.

 

가장 먼저 살펴볼 알고리즘은 버블 정렬이다.

 

1. 기본 컨셉

 - 버블 정렬은 인접해 있는 두 수를 비교해서 보다 큰 수를 뒤쪽으로 보내는 정렬 방식이다. 버블 정렬을 소개하는 간단한 동영상을 살펴보면 구현 방식을 아주 쉽게 알 수 있다. (50초 부터가 정렬 과정이다.)

https://www.youtube.com/watch?v=lyZQPjUT5B4

 - 동영상 내용을 보면 알 수 있듯이 언제나 두 데이터가 나와서 경합을 펼치며 큰 수가 뒤로 이동한다. 한 싸이클이 끝나면 맨 뒤에는 가장 큰 수가 위치하게 된다. (동영상에서는 확정된 값들을 뒤돌아버린다.)

 

 - 다음 반복은 역시 앞에서 부터 쭉~ 진행되는데 이미 정렬된 데이터 앞까지 만 진행하면 된다.

 

 - 가장 간단한 정렬 방식으로 구현또한 단순하다. 아래 정렬 과정을 살펴보자.

 

2. 정렬 과정

첫 번째 단계에서 맨 마지막의 9가 확정된다.

 

이어서 두 번째 단계에서 8이 확정된다.

 

이런 과정을 거쳐 뒤에서 부터 정렬이 완성된다.

 

위와 같은 과정을 거쳐 버블 정렬이 진행된다. 이를 실제 코드로 살펴보자.

 

3. 자바 코드

@Test
public void bubbleSortTest() {
	data = new int[] { 3, 0, 1, 8, 7, 2, 5, 4, 6, 9 };
	for (int i = 0; i < data.length; i++) {
		// 한바퀴 돌 때마다 맨 뒤 숫자가 결정된다.
		for (int j = 0; j < data.length - 1 - i; j++) {
			// 앞 요소가 더 크면 뒤 요소와 swap한다.
			if (data[j] > data[j + 1]) {
				int temp = data[j];
				data[j] = data[j + 1];
				data[j + 1] = temp;
			}
		}
		System.out.printf("%d단계: %s%n", i, Arrays.toString(data));
	}
	System.out.printf("bubble sort: %s%n", Arrays.toString(data));
}

출력 결과는 아래와 같다.

0단계: [0, 1, 3, 7, 2, 5, 4, 6, 8, 9]
1단계: [0, 1, 3, 2, 5, 4, 6, 7, 8, 9]
2단계: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
3단계: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
4단계: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
5단계: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
6단계: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
7단계: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
8단계: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
9단계: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
bubble sort: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

4. 정리

버블 정렬은 외부 반복문(O(n))과 내부 반복문(O(n))이 돌기 때문에 시간 복잡도는 O(n^2)으로 느린 알고리즘이다.

데이터가 적을 때는 상관 없겠지만 데이터가 많아지면 급격히 연산 회수가 늘어나므로 조심해야 한다.

 

코드가 이해하기 쉽고 단순하다는 점 말고는 장점이 없다고 볼 수 있다.