[Algorithm] 거품 정렬(Bubble Sort)

안녕하세요. 신뇽이 되고싶은 미뇽입니다!

오늘은 정렬 알고리즘 중 거품 정렬에 대해 알아보도록 하겠습니다!

 

거품 정렬

- 두개의 인접한 원소를 비교하여 정렬하는 방식입니다.

- 비교정렬이며, 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 제자리 정렬입니다.

 

 

정렬 방법

1. 앞에서부터 현재 원소와 바로 다음의 원소를 비교합니다.

2. 현재 원소가 다음 원소보다 크면 원소를 교환합니다.

3. 다음 원소로 이동하여 해당 원소와 그 다음원소를 비교합니다.

 

 

이 때, 각 라운드를 진행 할 때마다 뒤에서부터 한 개씩 정렬되기 때문에, 한번씩 줄면서 비교하게 됩니다.

 

 

구현

public class Bubble_Sort {
 
	public static void bubble_sort(int[] a) {
		bubble_sort(a, a.length);
	}
	
	private static void bubble_sort(int[] a, int size) {
		
		// round는 배열 크기 - 1 만큼 진행됨 
		for(int i = 1; i < size; i++) {
			
			// 각 라운드별 비교횟수는 배열 크기의 현재 라운드를 뺀 만큼 비교함
			for(int j = 0; j < size - i; j++) {
				
				/*
				 *  현재 원소가 다음 원소보다 클 경우
				 *  서로 원소의 위치를 교환한다. 
				 */
				if(a[j] > a [j + 1]) {
					swap(a, j, j + 1);
				}
			}
		}
	}
	
	private static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

 

시간 복잡도

O(N^2)

 

[장점]

1. 추가적인 메모리 소비가 작습니다.

2. 구현이 매우 쉽습니다.

3. 안정정렬이 가능합니다.

 

[단점]

1. 다른 정렬 알고리즘에 비해 교환 과정이 많아 많은 시간을 소비합니다.

 

 

 

최선의 경우 시간복잡도를  O(N)로 만드는 방법

 

각 라운드에서 비교수행을 할 때 원소가 교환되지 않는다면, 즉 swap이 발생하지 않는다면 이는 이미 정렬된 데이터라는 의미이기 때문에 정렬을 종료하면 됩니다.

즉, 각 라운드에서 비교수행을 했는지를 판단할 수 있는 변수를 하나 두면 됩니다.

 

구현 코드

public class Bubble_Sort {
 
	public static void bubble_sort(int[] a) {
		bubble_sort(a, a.length);
	}
	
	private static void bubble_sort(int[] a, int size) {
		
		// round는 배열 크기 - 1 만큼 진행됨 
		for(int i = 1; i < size; i++) {
        
			boolean swapped = false;	
			
			// 각 라운드별 비교횟수는 배열 크기의 현재 라운드를 뺀 만큼 비교함
			for(int j = 0; j < size - i; j++) {
				
				/*
				 *  현재 원소가 다음 원소보다 클 경우
				 *  서로 원소의 위치를 교환하고
				 *  비교수행을 했다는 표시로 swapped 변수를 true로 변경한다.
				 */
				if(a[j] > a [j + 1]) {
					swap(a, j, j + 1);
					swapped = true;
				}
			}
            
			/*
			 * 만약 swap된적이 없다면 이미 정렬되었다는 의미이므로
			 * 반복문을 종료한다. 
			 */
			if(swapped == false) {
				break;
			}
		}
	}
	
	private static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

이렇게 하면, 성능을 조금 개선시켜 이미 정렬된 경우 첫 라운드에서 탐색을 하고 바로 종료가 됩니다.

 

 

때문에 가끔 검색해보면 Bubble Sort 의 최선의 경우가 O(N)으로 표기하기도 하고, O(N2) 으로 표기하기도 하는데, 일반적으로 swap 여부를 판단 할 수 있는 변수를 두지 않고 하는 구현의 경우는 O(N2), swap여부를 판단할 수 있는 변수를 둔 경우 O(N)이라고 보면 됩니다.

 

출처:

https://st-lab.tistory.com/195

자바 [JAVA] - 거품 정렬 (Bubble Sort)