[자바] 버블 정렬(Bubble Sort)

버블정렬

버블 정렬이란 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 단순한 알고리즘입니다.

예시를 들어 버블 정렬에 대해 알아보겠습니다.

먼저 끝에 있는 두 요소 9와 8부터 대소를 비교합니다. 이때 오름차순이라면 왼쪽의 값이 작아야 하고 내림차순이라면 왼쪽의 값이 더 커야 합니다. 오름차순으로 정렬을 할 것이기 때문에 9와 8을 교환하면 아래와 같은 배열이 됩니다.

그다음 1와 8을 비교합니다. 1은 8보다 작기 때문에 교환할 필요가 없습니다. 따라서 그 다음 요소를 비교하교 이렇게 첫 번째 요소까지 작업을 계속한다면 아래와 같은 순서로 정렬이 되게 됩니다.

요소의 개수가 N개인 배열에서는 N-1회를 비교하게 되고 끝에서 끝까지 교환하는 작업을 패스(pass)라고 합니다.

그리고 패스가 한번 수행될 때마다 정렬할 요소가 하나씩 줄어들기 때문에 두 번째 패스의 비교 횟수는 N-2회입니다.

 

그리고 모든 정렬이 끝나려면 N-1회의 패스가 수행되어야 합니다.

 

버블 정렬을 코드로 구현해보도록 하겠습니다.

 

먼저 배열 속의 두 요소를 교환하는 swap() 메서드입니다.

	static void swap (int[] a, int idx1, int idx2) {
		int temp = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = temp;
	}

 

다음으로는 배열을 버블 정렬시키는 bubbleSort() 메서드입니다.

	static void bubbleSort(int[] a, int n) {
		for(int i = 0 ; i < n - 1 ; i++) { // 배열의 크기 N - 1 만큼 패스 작업
			for(int j = n - 1 ; j > i ; j--) { // 배열의 끝 n-1 부터 비교
				if (a[j - 1] > a[j]) { // 대소비교
					swap(a, j-1, j); // 교환
				}
			}
		}
	}

위에서 설명한 것처럼 n - 1회의 패스가 수행됩니다.

배열의 끝 요소인 n - 1부터 비교를 하여 j > i까지 비교합니다. 여기서 j > i 까지 비교하는 이유는 각 패스에서 정렬이 정상적으로 수행되었다면 j < i 인 요소들은 정렬이 끝난 상태이기 때문입니다.

 

여기까지 오셨다면 이런 생각을 하시게 될 겁니다.

"n - 1회 패스 작업을 하는 것은 너무 비효율적이다. 중간에 정렬이 끝날 수도 있다."

 

이미 배열이 오름차순으로 정렬이 된 상태라면 그 이후의 패스는 요소를 교환하지 않습니다.

따라서 교환 횟수를 체크하여 버블 정렬을 빠져나가도록 코드를 수정합니다.

	// 버블 정렬
	static void bubbleSort(int[] a, int n) {
		for (int i = 0; i < n - 1; i++) { // 배열의 크기 N - 1 만큼 패스 작업
			int check = 0;
			for (int j = n - 1; j > i; j--) { // 배열의 끝 n-1 부터 비교
				if (a[j - 1] > a[j]) { // 대소비교
					swap(a, j - 1, j); // 교환
					check++;
				}
			}
			if (check == 0) { // 교환 횟수가 0번이라면 반복문을 빠져나감
				break;
			}
		}
	}

 

위의 개선한 코드는 모든 요소들이 정렬되어 있을 때 프로그램을 종료합니다.

하지만, 앞쪽 k개의 요소가 정렬되어 있다면 매번 패스 때마다 k개의 요소를 비교하는 것은 매우 비효율적입니다.

 

예를 들어 한 번의 패스를 통해서 아래의 그림처럼 되었다면

 

매번 패스 때마다 1, 2, 3을 비교하는 것은 비효율적입니다.

위의 내용을 바탕으로 코드를 새롭게 수정합니다.

	// 버블 정렬
	static void bubbleSort(int[] a, int n) {
		int k = 0 ; // 첫 패스에는 모든 요소를 검사
		while(k < n - 1) {
			int last = n - 1; // 마지막으로 교환한 요소 위치
			for (int j = n - 1; j > k; j--) { // 배열의 끝 n-1 부터 비교
				if (a[j - 1] > a[j]) { // 대소비교
					swap(a, j - 1, j); // 교환
					last = j;
				}
			}
			k = last; // 마지막으로 교환한 위치를 k에 저장
		}
	}

패스를 한번 진행할 때 마지막으로 교환한 위치를 k에 저장한다면

앞쪽에 정렬이 되어있으면 교환하지 않기 때문에 다음 패스에서는 정렬되어 있는 앞쪽은 패스를 건너뛰게 됩니다.

 

만약 모든 요소가 정렬되어 있다면 마지막으로 교환한 위치가 n - 1이 되기 때문에 프로그램이 종료됩니다.

 

package bubblesort;

public class BubbleSort {

	static void swap(int[] a, int idx1, int idx2) {
		int temp = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = temp;
	}

	// 버블 정렬
	static void bubbleSort(int[] a, int n) {
		int k = 0 ; // 첫 패스에는 모든 요소를 검사
		while(k < n - 1) {
			int last = n - 1; // 마지막으로 교환한 요소 위치
			for (int j = n - 1; j > k; j--) { // 배열의 끝 n-1 부터 비교
				if (a[j - 1] > a[j]) { // 대소비교
					swap(a, j - 1, j); // 교환
					last = j;
				}
			}
			k = last; // 마지막으로 교환한 위치를 k에 저장
		}
	}
}