[알고리즘] 버블정렬 개선하기

버블정렬에 관한 포스팅에 이어 작성함

알고리즘 개선 1

다음과 같은 배열이 있다.
1 3 6 4 7 8 9

이전에 작성한 버블정렬로 위 배열을 정렬하다가 세번째 패스에 도달하였다고 생각해보자

세번째 pass를 진행할것이므로 앞에서부터 2개의 요소는 이미 정렬이 되어있을 것이다.

3번째 패스의 모든 과정들을 나열하면 아래와 같다.
1 3 6 4 7 8 9 => 8과 9를 비교. 교환은 이루어지지 않음
1 3 6 4 7 8 9 => 7과 8을 비교. 역시 교환은 x
1 3 6 4 7 8 9 => 4와 7을 비교. 교환 x
1 3 4 6 7 8 9 => 4와 6을 비교. 교환이 이루어짐

그리고 이어 4번째 pass를 진행을 해보면 해당 pass에선 교환이 아예 일어나질 않는다.
배열이 정렬을 마친 상태라면 이후의 패스는 요소 교환을 하지 않는다는 것을 알 수 있다.

기존의 알고리즘은 이 상황에서 끝까지 비교작업을 수행을 하게 되고 이는 결국 비효율적이라는 것이다.

따라서 개선된 정렬 메서드를 다음과 같이 작성하였다.

public static void bubbleSort2(int[] a, int n) {
	for(int i = 0; i<n-1; i++) {
		int exchg = 0; //해당 패스에서 일어난 교환횟수 체크
		for(int j = n-1; j>i; j--) {
			if(a[j-1] > a[j]) {
				swap(a, j, j-1);
				exchg++;
			}
		}
		if(exchg == 0) {
			break; // 교환이 일어나지않았다면 정렬이 완료되었다고 간주
		}
	}
}

알고리즘 개선 2

다음과 같은 배열을 버블정렬 수행한다고 가정해보자.
1 3 9 4 7 8 6

버블정렬의 첫번째 패스를 나타내본다.
1 3 9 4 7 8 6 => 8과 6 비교. 교환 o
1 3 9 4 7 6 8 => 7과 6 비교. 교환 o
1 3 9 4 6 7 8 => 4과 6 비교. 교환 x
1 3 9 4 6 7 8 => 9과 4 비교. 교환 o --- 마지막 교환
1 3 4 9 6 7 8 => 3과 4 비교. 교환 x
1 3 4 9 6 7 8 => 1과 3 비교. 교환 x

위 교환과정을 보면 9와 4를 비교하고나서 그 이후의 단계에선 교환이 더이상 발생하질 않는다. 저 pass가 끝나고 그 다음 pass에서는 마지막 교환 발생지점 이후의 요소들 (1, 3, 4) 에 대해서는 비교를 할 필요가 없다는 것이다.

이번 개선한 알고리즘의 핵심은
마지막으로 교환한 요소의 인덱스를 기준으로 다음에 수행할 패스의 범위를 제한하는 것이다.

public static void bubbleSort3(int[] a, int n) {
	// a[k] 앞쪽은 정렬을 마친 상태 
	// 0으로 초기화 한 이유? 첫번째 패스에선 모든 요소 검사
	int k = 0; 		
	while(k < n-1) {
		int last = n - 1;
		for(int j=n-1; j>k; j--) {
			if(a[j-1] > a[j]) {
				swap(a, j-1, j);
				last = j;
			}
		}
		k = last;
	}
}

last 변수는 마지막으로 교환한 두 요소에서 오른쪽 요소의 인덱스를 저장한다. 하나의 pass가 완료되면 k에 last값을 대입하고 다음에 행할 pass 범위를 제한한다.
다음 pass에서 마지막으로 비교할 두 요소는 a[k] 와 a[k+1] 이 된다.

양방향 버블 정렬

버블정렬을 개선시켜 만든 이 정렬 알고리즘은 양방향 버블정렬, 칵테일 정렬 혹은 쉐이커 정렬 이라는 이름들을 가지고 있다.

패스가 일어날때마다 스캔방향을 바꾸는것이다.
홀수번째 패스 : 가장 작은 요소를 맨 앞으로
짝수번째 패스 : 가장 큰 요소를 맨 뒤로

static void shakerSort(int[] a, int n) {
	int left = 0;
	int right = n - 1;
	int last = right;

	while (left < right) {
		for (int j = right; j > left; j--) {
			if (a[j - 1] > a[j]) {
				swap(a, j - 1, j);
				last = j;
			}
		}
		left = last;

		for (int j = left; j < right; j++) {
			if (a[j] > a[j + 1]) {
				swap(a, j, j + 1);
				last = j;
			}
		}
		right = last;
	}
}