[알고리즘] 버블 정렬(bubble sort) 란?

- 버블 정렬이란 무엇인가?

 버블 정렬은 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 정렬이다.

 위의 배열에서 첫 째 pass에서는 배열의 [0]과 [1]번째 인덱스를 비교하여 오름 차순이 아닐경우 두 배열의 순서를 바꾸어 준다 (swap) 이를 [0] ~ [1]의 비교에서 [n - 2] ~ [n - 1]까지의 비교를 통해서 배열에서 제일 큰 값을 배열의 마지막에 저장을 하고 둘 째 pass에서는 첫 째 pass와 같이 [0] ~ [1]의 비교에서  [n - 3] ~ [n - 2]까지 비교를 통해서 배열에서 둘 째로 큰 값을 정렬한다. 이와같은 방법으로 총 (n - 1)번의 pass를 지나면 버블 정렬이 완료된다.

 

 

 

- 버블 정렬 구현 ver.1

 본 포스트에서는 버블 위에서 설명한 인덱스가 적은 것에서 부터 시작이 아니라 [n], 마지막 인덱스부터 시작하는 버블 정렬을 구현하고자 한다.

 구현을 하고자 하는 버블 정렬은 다음과 같다.

for (int i = 0; i < n - 1; i++) {
 // a[i], a[i + 1], ... , a[n - 1]에 대해서 앞쪽으로 스캔하며 두 요소씩 비교한 후 교환
 }

 총 (n - 1)번의 pass를 수행하면 되므로 for문의 조건을 'i < n - 1'로 설정하였다. for 문안에서 인접한 두 요소의 인덱스는 for 문을 사용해서 (n - 1)에서 부터 시작을 하면 다음과 같다

static void bubbleSort(int[] a, int n) { // a는 정렬할 배열, n은 배열의 요솟수
	for (int i = 0; i < n - 1; i++) {
		for (int j = n - 1; j > i; j--)
    		if (a[j - 1] > a[j])
        		swap(a, j - 1, j); // 배열 a의 j - 1인덱스의 값과 j인덱스의 값의 교환하는 함수
    	}
}

 swap 함수는 다음과 같다.

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

 

 

 

- 버블 정렬 구현 ver.2

  하지만 ver.1의 버블 정렬은 불필요한 요소 비교가 이루어 질 수 있다.

 위의 그림을 보면 위의 요소수 7의 배열에서 1, 2, 4는 정렬이 완료 되었고 pass 4번째 에서 문제가 발생하는데 [5] ~ [6]의 비교, [4] ~ [5], [3] ~ [4]의 비교에서 이미 정렬이 되어 교환이 필요하지 않고 다음 5번째 pass에서도 불필요한 비교를 할 예정이다. 이런 불필요한 요소의 비교를 하지 않기 위해서 나온 발전된 버블 정렬 알고리즘은 다음과 같다.

static void bubbleSort(int[] a, int n) {
	for (int i = 0; i < n; i++) {
    		int exchg = 0; // 교환의 횟수를 pass때마다 0으로 초기화 한다
        	for (int j = n - 1; j > i; j--) {
        		if (a[j] < a[j -1]) { // 교환 조건
            			swap(a, j, j - 1);
                		exchg++; // 교환이 이루어지면 exchg변수를 1 증가한다
            		}
        }
        if (exchg == 0) // 교환이 되지 않으면 이미 정렬이 이루어 졌다고 판단
        	break;
    }
}

위의 알고리즘에서는 exchg 변수를 통해서 교환이 이루어 졌는지를 판단해 불필요한 요소 비교를 줄였다.

 

 

 

- 버블 정렬 구현 ver.3

 

 위의 그림을 보면 첫 번째 pass에서 1, 2, 4번째 비교에서만 교환이 이루어져 4번째 비교 후로 5, 6번째 비교에서는 이미 정렬이 되어 교환을 하지 않았다. 그렇다면 두 번 째 pass에서 [0] ~ [2] 까지의 비교는 무의미한 연산으로 인한 낭비가 있기에 앞전 pass에서 마지막에서의 교환 여부를 확인하여 다음 pass로 건내주어 알고리즘의 개선을 할 수 있다.

static void bubbleSort(int[] a, int n) {
	int k = 0; // k의 앞쪽은 이미 정렬이 완료 되었다
    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;
    }
}

 위의 알고리즘에서는 k 변수를 통해서 어디까지 정렬이 완료 되었는지 저장하여  pass당 [n - 1] ~ [k]까지 비교연산을 진행한다.

 

 

 

- 양방향 버블 정렬 (bidirection bubble sort) 

 위에서 나온 배열을 살펴보자.

 위의 배열을 [0]을 제외한 [1] 에서 [6]까지 모두 오름차순으로 정렬이 되어 있지만 [0]이 배열의 요소중에서 가장 크다는 이유로 한칸씩 뒤로 옮기는 버블 정렬에서는 앞서 설명한 발전된 ver.3의 버블 정렬을 사용해도 빠른 시간내에 정렬 작업을 할 수 없다. 하지만 양방향 버블 정렬 (bidirection bubble sort) 또는 칵테일 정렬(cocktail sort)라고 부르는 정렬을 사용하면 더 적은 횟수로 정렬을 완료 할 수 있다.

 

 양방향 버블 정렬이란, 홀수 번째의 패스는 가장 작은 요소를 맨 앞으로 옮기고 짝수 번째 패스는 가장 큰 요소를 맨 뒤로 옮기는 방식을 사용하면 된다.

static void biBubbleSort(int[] a, int n) {
        int left = 0; // 홀수 패스의 몇 번째 까지 완료가 되었는지
        int right = n - 1; // 짝수 패스의 몇 번째 까지 완료가 되었는지
        int last = right;

        while (left < right) {
            for (int i = right; i > left; i--) { // 홀수 번째의 패스
                if (a[i] < a[i - 1]) {
                    swap(a, i, i - 1);
                    last = i;
                }
            }
            left = last;


            for (int i = left; i < right; i++) { // 짝수 번째의 패스
                if (a[i] > a[i + 1]) {
                    swap(a, i, i + 1);
                    last = i;
                }
            }
            right = last;

        }
    }

 위의 알고리즘을 보면 버블 정렬 ver.3와 알고리즘 양상은 비슷하다, k 대신에 left, right 변수를 써서 배열의 양쪽의 정렬을 모두 확인한다는 점에서 차이가 있다.