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

 

[정렬 알고리즘 모음]

 

 

1. 계수 정렬 (Counting Sort)

2. 선택 정렬 (Selection Sort)

3. 삽입 정렬 (Insertion Sort)

4. 거품 정렬 (Bubble Sort) - [현재 페이지]

5. 셸 정렬 (Shell Sort)

6. 힙 정렬 (Heap Sort)

7. 합병(병합) 정렬 (Merge Sort)

8. 퀵 정렬 (Quick Sort)

9. 이진 삽입 정렬 (Binary Insertion Sort)

10. 팀 정렬 (Tim Sort)

 

 

 

 

 

 

 

 

 

• Bubble Sort [거품 정렬]

 

 

 

거품 정렬은 아마 정렬 방식 중 가장 쉽게 생각할 수 있는 알고리즘 중 하나일 것이다.

 

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

왜 Bubble 이라는 이름이 붙었는지 찾아보니 정렬 과정에서 원소의 이동이 마치 거품이 수면위로 올라오는 것 같다고 해서 거품(Bubble) 이라는 이름이 붙었다고 한다...

 

 

정렬 방식 중 가장 쉬우니 일단 거품 정렬에 대한 특징만 짚고 넘어가보자.

 

거품 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다. 이는 선택정렬과도 같은 부분이다.

 

그리고 이전에 다뤘던 선택 정렬과는 달리 거품 정렬은 앞에서부터 차례대로 비교하기 때문에 '안정 정렬'이기도 하다.

 

 

 

 

 

 

 

 

 

---

• 정렬 방법

 

 

 

 

 

거품 정렬의 전체적인 과정은 이렇다. (오름차순을 기준으로 설명)

 

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

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

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

 

 

 

즉, 그림으로 보면 다음과 같은 과정을 거친다.

 

 

 

 

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

한마디로 정리하자면 이렇다.

총 라운드는 배열 크기 - 1 번 진행되고,

각 라운드별 비교 횟수는 배열 크기 - 라운드 횟수 만큼 비교한다.

 

 

 

 

 

전체적인 흐름을 보자면 다음과 같은 형태로 정렬 한다.

 

https://en.wikipedia.org/wiki/Bubble_sort

 

 

https://ko.wikipedia.org/wiki/거품_정렬

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

그 외에도 많은 참고 영상들이 있는데, 영상으로 보는 것이 더 쉬울 것 같아 같이 첨부하도록 하겠다.

 

 

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

 

 

 

 

 

 

 

 

 

 

---

• Bubble Sort 구현하기

 

 

 

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;
	}
}

 

 

 

구현 자체는 어렵지 않을 것이다.

 

 

 

 

 

 

 

 

---

 

• 거품 정렬의 장점 및 단점

[장점]

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

2. 구현이 매우 쉽다.

3. 안정정렬이 가능하다.

 

 

[단점]

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

 

 

 

 

 

시간복잡도에 대해 잠깐 언급하자면, 위 알고리즘에서도 볼 수 있듯, 초기 배열에서 3과 5의 경우 원래 해당 자리에 맞는 위치지만, 교환과정에서 중간에 한 번씩 맞지 않은 자리임에도 이동하게 된다.

또한 다른 정렬 알고리즘보다 값 교환 과정이 많기 때문에 그만큼 효율성도 떨어져 가장 배우기 쉽고, 구현하기 쉬움에도 사실상 쓰이지 않는 정렬 방법이기도 하다.

 

 

 

그럼 시간 복잡도는? 이라는 질문이라면 거품 정렬의 평균 시간 복잡도 또한 O(N²)의 시간 복잡도를 갖는다.

 

공식을 유도해보자면 이렇다. 

N이 정렬해야하는 리스트의 자료 수, i가 라운드라고 할 때 loop(반복문)을 생각해보자.

 

i=1  일 때, 데이터 비교 횟수는 N-1 번

i=2 일 때, 데이터 비교 횟수는 N-2 번

i=3 일 때, 데이터 비교 횟수는 N-3 번

                   ⋮

i = N-1 일 때, 데이터 비교 횟수는 1 번

 

 

즉, 다음과 같이 일반화하여 공식으로 만들 수 있다.

그리고 N에 대하여 다음을 만족하기 때문에 시간복잡도 또한 도출 할 수 있다.

 

 

 

즉, 시간복잡도는 O(N²)이다.

 

 

 

다만, 하나 포인트를 짚고 가자면 최선의 경우(Best Case)일 경우다. 거품 정렬의 경우 크게 두 가지로 나뉘는데, 위 처럼 일반적인 구현의 경우에는 최선의 경우에도 O(N²) 가 맞다. 어찌되었건 비교수행에 있어 이미 정렬되었더라도 각 라운드별로 반복 비교를 하기 때문이다.

 

하지만, 여기서 최선의 경우 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(N²) 으로 표기하기도 하는데, 일반적으로 swap 여부를 판단 할 수 있는 변수를 두지 않고 하는 구현의 경우는 O(N²), swap여부를 판단할 수 있는 변수를 둔 경우 O(N)이라고 보면 된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

 

• 정리

 

 

거품정렬의 경우 사실상 거의 쓰이지는 않는 정렬 알고리즘이지만, 반대로 가장 기초적인 정렬 알고리즘이기도 하다. 보통 정렬 알고리즘에 대해 배우면 거품정렬부터 배울 것이다.

 

하지만 삽입정렬이나 선택정렬과 같은 O(N²) 의 시간복잡도를 갖는다 하더라도 거품정렬의 교환횟수가 평균적으로 더 많기 때문에 실질적으로는 삽입, 선택 정렬보다 더 많은 시간이 걸린다.  

 

 

이전에 다뤘던 정렬 알고리즘과 앞으로 다룰 정렬 알고리즘들의 정렬 별 성능표는 아래와 같다..

필자가 테스트 한 결과로 Bubble sort는 29초대에 자리하고 있다. (컴퓨터의 환경에 따라 달라질 수 있다) 필자가 테스트한 정렬 알고리즘 중 가장 좋지 않은 성능을 보이고 있다.

 

 

 

 

또한 각 정렬 알고리즘 별 시간 복잡도와 평균 정렬 속도는 다음과 같다.

 

이후에 차근차근 구현해보겠지만, 각 알고리즘마다 최상과 평균 시간복잡도와 안정성은 어느정도 알고있는 것이 좋다. 

(참고로 Shell Sort의 경우 /가 나눗셈을 의미하는게 아니라 갭 시퀀스(gap sequence)에 따라 시간복잡도가 달라진다. 그래서 'gap sequence가 좋은 경우' / 'gap sequence가 나쁜 경우' 이렇게 보면 된다. 자세한 내용은 shell sort를 다룰 때 말해드리겠다.)

 

 

 

만약 여러분이 정렬 알고리즘에서 거품정렬을 배울 때 이렇게 swap에 대한 flag변수를 두지 않는다면, 최선의 경우에도 O(N²)의 시간 복잡도를 갖기 때문에 반드시 확인해보는 것이 좋다.

 

 

 

 

 

이번 거품 정렬은 매우 기초적인 정렬 방법 중 하나다. 아마 구현 자체는 그리 어렵지 않게 구현 할 수 있어 쉽게 이해했을 것이다. 

혹여 부족한 부분이 있거나 궁금한 점, 모르거나 이해가 가지 않는 부분이 있다면 언제든 댓글 달아주시면 감사하겠다.

 

 

그 외에 필자가 여러 타입들에 대해 구현 한 정렬 알고리즘 소스 코드들을 자세히 보고싶다면 아래 깃허브 repo에 업로드되어있으니 이를 참고하시길 바란다.

 

 

https://github.com/kdgyun/Sorting_Algorithm.git

kdgyun/Sorting_Algorithm