[Java]버블 정렬(Bubble Sort)

*버블 정렬(Bubble Sort)

->버블 정렬이란 인접한 두 원소를 비교하며, 큰 수를 계속하여 뒤로 보내 정렬하는 방식을 사용(오름 차순으로 정렬하는 경우)하는 정렬 방식이다.

->원소들이 거품이 올라오는 것처럼 보여 거품 정렬(Bubble Sort)이라고 이름지었다.

 

*버블 정렬의 이해

->어떤 대상을 '오름차순'으로 정렬할 때 버블 정렬은 원소를 처음부터 탐색하면서, 큰 수를 계속하여 뒤로 밀어내는 방식을 사용한다. 예를 들어 [5, 3, 1, 10, 7]이라는 배열을 버블 정렬을 이용하여 오름차순 정렬을 해보면 다음과 같다.

초기 배열 상태

 먼저, Array[0]와 Array[1]을 비교해보자. Array[0]가 Array[1]보다 크기 때문에, 이 두 배열의 원소의 위치를 바꾸어준다.

Array[0]와 Array[1]을 비교하고, 앞의 원소가 더 크다면 두 원소의 자리를 바꾸어준다.

 다음으로 Array[1]과 Array[2]를 비교해보자. 마찬가지로 Array[1]이 Array[2]보다 크기 때문에, 이 두 배열의 원소의 위치를 바꾸어준다.

Array[1]과 Array[2]를 비교하고, 앞의 원소가 더 크다면 두 원소의 자리를 바꾸어준다.

 다음으로 Array[2]와 Array[3]을 비교해보자. 이때, Array[2]는 Array[3]보다 작기 때문에 두 원소의 자리를 바꾸지 않는다.

Array[2]은 Array[3]보다 크기 않으므로, 자리를 교체하지 않는다.

마지막으로 Array[3]과 Array[4]를 비교해보자. Array[3]은 Array[4]보다 크기 때문에, 두 원소의 자리를 바꾸어준다.

Array[3]은 Array[4]보다 크기 때문에, 두 원소의 자리를 교체해준다.

 이렇게 순차적으로 한 번의 자리 교체가 완료되면, 가장 큰 수가 배열의 가장 뒤로 보내진 것을 확인할 수 있다. 따라서 이러한 점을 이용하여, 이 과정을 (배열의 크기 - 1)번 반복해주면 한 번의 반복마다 순차적으로 큰 수가 뒤로 밀리는 것을 보장할 수 있다. 즉, 모든 반복이 완료되면 배열의 모든 수는 오름차순으로 정렬이 될 것이다.

 

*버블 정렬의 구현

->다만 이 과정에서 이미 뒤로 보내진 수들은 다시 정렬 여부를 확인할 필요가 없기 때문에, 한 번의 반복마다 교체를 확인하는 인덱스를 1씩 줄여주며 반복을 하는 구현 방법을 주로 사용한다. 

package sort;

import java.util.Arrays;

public class BubbleSort {
	static int[] nums;

	public static void main(String[] args) {
		nums = new int[10];
		for (int i = 0; i < 10; i++) {
			nums[i] = (int) (Math.random() * 10);
		}
		System.out.println("<정렬 전>");
		System.out.println(Arrays.toString(nums));
		
		// 한 번의 반복이 완료될 때 마다 가장 큰 수는 배열의 가장 마지막 부분으로 밀리는 것이 보장된다.
		for(int i = nums.length - 1; i > 0; i--) {
			// 따라서, 한 번의 반복마다 가장 뒤의 인덱스는 비교하지 않도록 반복문을 설계할 수 있다.
			for(int j = 0; j < i; j++) {
				// 만일, 앞의 수가 뒤의 수보다 더 크다면 swap 연산을 진행해준다.
				if(nums[j] > nums[j + 1]) {
					int temp = nums[j];
					nums[j] = nums[j + 1];
					nums[j + 1] = temp;
				}
			}
		}
		
		System.out.println("<정렬 후>");
		System.out.println(Arrays.toString(nums));
	}
}

결과

*버블 정렬의 시간 복잡도

->위의 구현을 따르면 n - 1번의 교체작업부터 순차적으로 1번의 교체작업까지 반복하므로, 총 반복 횟수 = 1 + 2 + ... + (n - 1)의 형태를 가질 것이다. 즉, 총 반복 횟수 = n(n- 1)/2가 될 것이다. 따라서, 버블 정렬의 시간 복잡도는 O(n^2)이다.

->가장 큰 수를 뒤로 보내는 방식을 사용하기 때문에, 이미 정렬하고자 하는 배열이 어느정도 정렬이 되어 있는 상태 일수록 최선의 성능을 낼 수 있다.

->직관적으로 이해가 쉬운 정렬로 구현하기 쉽지만 일반적으로 O(n^2)의 시간복잡도를 갖기 때문에 실전에서는 거의 사용할 일이 없다. 다만 버블 정렬에 사용되는 Swap연산이 중요하기 때문에 초기 프로그래밍시 자주 사용되는 예제 중 하나이다.