[알고리즘 개념] 버블정렬, 자바

왜 이름이 거품정렬일까?

 

프로그래밍에서 변수나 메서드의 이름을 지을때는 그 역할을 명확하게 표현하게끔 짓는다고 했다. 근데 이 정렬은 왜 버블(거품)정렬일까. 나 같은 사람이 한명은 아닐 것 같아서 구글링을 했다. 

 

https://stackoverflow.com/questions/31059479/why-bubble-sort-is-called-bubble-sort

 

 "배열에서 요소의 이동이 물에서 거품의 움직임과 비슷하기 때문이다"라고한다. 그러니까 큰 거품이 제일 먼저 올라가는 것 처럼 가장 큰 요소가 가장 먼저 정렬이 된다. 이런 뜻인 것 같은데 글쎄. 

 

개념

 가장 큰 거품이 가장 먼저 올라간다는 이반 무쉬케티크(?)아저씨의 말처럼 버블정렬은 가장 큰 요소(반대로 가장 작은 요소가 먼저 일 수도 있다) 가 가장 먼저 정렬이 되는 알고리즘이다. 즉 오름차순(혹은 내림차순)으로 정렬을 한다는 내용이다. 

 

 오름차순을 구현하는 방법은 간단하다. 이웃하는 두 개의 요소를 비교해서 큰 값을 오른쪽으로, 작은 값을 왼쪽으로 swap하는 것이다. 

 

예

 예를 들어 8, 9, 5, 2 를 정렬한다고 해보자. 그럼 맨 처음 8과 9를 비교한다. 왼쪽요소<오른쪽 요소 이므로 정렬할 필요가 없다. 그 다음 9, 5를 비교해보자 왼쪽요소> 오른쪽요소 이므로 두개 요소의 위치를 바꿔야한다. 결과는 8, 5, 9, 2가 된다. 그 다음 9, 2를 비교해보자. 왼쪽요소 > 오른쪽 요소이므로 두개 요소의 위치를 바꿔야 한다. 결과는 8, 5, 2, 9가 된다.  한 바퀴를 돌린 결과 맨 처음 리스트 8,9,5,2 에서 가장 큰 값이 9가 배열의 맨 마지막으로 이동했다. 

 

 두바퀴에서는 첫번째 바퀴에서 정렬이 완료된 9를 제외한 8,5,2를 가지고 첫번째에서 했던 패턴을 반복한다. 마찬가지로 두바퀴가 끝난 시점에는 8,5,2 중 가장 큰 값인 8이 배열의 맨 마지막으로 정렬되어 있을 것이다. 결과는 5,2,8

 

세번째 바퀴에서는 두번째 바퀴에서 정렬이 끝난 8을 제외한 5,2를 가지고서 패턴을 반복한다. 그러면 5, 2 중 큰 가장 큰 값인 5 가 맨 마지막으로 정렬되어 있을 것이다. 

 

 네번째 바퀴에서 남은 요소는 2가 된다. 정렬 할 요소가 없으므로 정렬을 끝낸다. 최종적으로 2,5,8,9로 정렬이 된다. 

 

 

 

https://commons.wikimedia.org/wiki/File:Bubble-sort.gif

 

구현 

길이가 5인 배열을 버블정렬 할 때, 각 n회차 반복에 비교하는 인덱스를 표로 나타내면 다음과 같다. 

n회	비교
0	(0,1) (1,2) (2,3) (3,4)
1	(0,1) (1,2) (2,3)
2	(0,1) (1,2)
3	(0,1)
4	끝

 

가장 바깥 반복(n회)은 리스트 길이의 -1 만큼 반복을 하고, 안쪽 반복(비교)  길이 - n -1 만큼 반복한다. 이걸 코드로 구현 하면 아래와 같다. 여기서는 자료형이 정수인 ArrayList를 매개변수로 받았다.

 

public static void BubbleSort(int[] list) {
		for(int i = 0; i<list.length-1; i++) {
			for(int j = 0; j<list.length-i-1 ; j++) {
				int left = list[j];
				int right = list[j+1];
				if(left>right) {
					list[j] =right;
					list[j+1]= left;		
				}
			}
		}
	}

코드 향상

  만약 123465 라는 리스트가 있을 경우, 위의 코드로 정렬을 하게 되면 첫번째 turn에서 123456으로 정렬이 되지만, 반복문을 계속진행하게 된다. 이 경우, 즉 정렬이 다 된경우  반복문을 멈추게 함으로써 시간을 단축시킬 수 있다. 

 

 구현방법은 한번의 turn을 돌았을때 정렬(left>right)인경우가 없으면 반복문을 그만두게 하면된다. 

public static void BubbleSortBoost(int[] list) {
		boolean isSorted = false;
		int bound =1;
		
		while(!isSorted) {
			isSorted = true;
			for(int index = 0 ; index <list.length - bound; index++) {
				if(list[index]>list[index+1]) {
					isSorted = false;
					int temp = list[index+1];
					list[index+1] = list[index];
					list[index] =temp;
				}
			}
			bound ++;
		}
	}

 

배열의 크기가 100,000인 배열을 각각 위의 버블정렬과 향상된 버블정렬로 돌려보면 

꽤나 많이 차이나는 것을 볼 수 있다. 

시간복잡도

 데이터 갯수에 따른 비교횟수를 표로 나타내면 아래와 같다.

데이터 수	비교횟수
1	1
2	1
3	2+1
4	3+2+1
5	4+3+2+4

데이터의 갯수가 n이면, n-1회 반복을 하는데 데이터의 길이가 1이 될때까지 반복을 하므로

1+2+3+ ...+n-1 = n(n-1)/2 회 비교를 한다. 따라서 시간복잡도는 O(n^2) 이 된다.