[알고리즘] 버블 정렬/Bubble Sort - 2 (+ 양방향 버블 정렬)

이전 버블정렬 글은 오름차순 기준에서 앞에서 뒤로( 큰 값의 요소를 끝으로 옮기는 과정 )의 예시이고, 이번에는 뒤에서 앞으로 ( 작은 값의 요소를 앞으로 옮기는 과정)의 예시 + 버블 정렬 알고리즘에 대한 개선 방안들에 대한 내용들도 추가되었다. 

 

#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)

// 오름차순, 뒤에서 앞으로 ( 각 패스에서 가장 작은 값의 요소가 맨 앞으로 옮겨짐 )
void bubble(int a[], int n) {
    int i, j;
    for(i = 0; i < n - 1; i++) {
        for(j = n - 1; j > i; j--) {
            if(a[j - 1] > a[j])
                swap(int, a[j - 1], a[j]);
        }
    }
}

 

 

서로 이웃한 요소에 대해서만 교환하므로 '버블 정렬' 알고리즘은 안정적이다.

 

총 패스는 n - 1 회이며, 각 패스에서의 수행 횟수는 n - k ( k는 패스 )이다.

 

시간복잡도 : O(n^2)

 

 

버블 정렬 알고리즘 개선 - 1, 패스 단위의 멈춤 도입

 

이미 배열이 정렬을 마친 상태라면( 패스 수행 결과 요소의 교환 횟수가 0이라면 ), 더 이상 정렬할 요소가 없다는 뜻이기 때문에 그 이후의 패스는 실행되지 않도록 개선.

#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)

// 오름차순, 뒤에서 앞으로 ( 각 패스에서 가장 작은 값의 요소가 맨 앞으로 옮겨짐 )
// 패스 단위의 멈춤 도입
void bubble(int a[], int n) {
    int i, j;
    for(i = 0; i < n - 1; i++) {
        int exchg = 0; // 패스에서 시도한 교환 횟수
        for(j = n - 1; j > i; j--) {
            if(a[j - 1] > a[j]) {
                swap(int, a[j - 1], a[j]);
                exchg++;
            }
        }
        if(exchg == 0) break; // 교환이 수행되지 않았다면 정렬을 멈춤
    }
}

 

이를 응용하여 배열이 정렬을 마쳤는지를 검사하는 함수를 만들 수 있다.

 

 

버블 정렬 알고리즘 개선 - 2, 패스 내부의 멈춤 도입

 

각각의 패스에서 비교, 교환을 하다가 어떤 시점 이후에 교환이 수행되지 않는다면, 그보다 앞쪽의 요소는 이미 정렬을 마친 상태임을 알 수 있다. 이를 생각하여 해당 부분을 제외한 요소들만 정렬을 시도하게끔 하여 과정을 줄인다.

#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)

// 오름차순, 뒤에서 앞으로 ( 각 패스에서 가장 작은 값의 요소가 맨 앞으로 옮겨짐 )
// 패스 내부의 멈춤 도입 (스캔 범위 제한)
void bubble(int a[], int n) {
    
    int k = 0; // a[k]보다 앞쪽의 요소는 정렬을 마친 상태. 스캔 범위 조정. 하지만 항상 시작은 n - 1임.
    
    while(k < n - 1) {
        int j;
        int last = n - 1; //마지막으로 교환을 수행한 위치 저장(두 요소 가운데 오른쪽 요소). 그대로 n - 1이라면, 정렬할 게 없다는 뜻이므로 종료.
        
        for(j = n - 1; j > k; j--) { // 참고로, 항상 j = n - 1부터 시작. 변하는건 앞쪽 k임.
            if(a[j - 1] > a[j]) {
                swap(int, a[j - 1], a[j]);
                last = j;
            }
        }
        k = last; // 각 패스에서 마지막 스캔 범위 제한. 하나의 패스를 마쳤을 때 last 값을 k에 대입하여 다음에 수행할 패스의 범위를 제한한다.
    }
}

 

 

버블 정렬 알고리즘 개선 - 3, 양방향 버블 정렬(bidrection bubble sort) / 칵테일 정렬(cocktail sort) / 쉐이커 정렬(shaker sort)

 

개선2의 '패스 내부 멈춤 도입' + 홀수 번째 패스는 가장 작은 요소를 맨 앞으로 옮김, 짝수 번째 패스는 가장 큰 요소를 맨 뒤로 옮김 (패스의 스캔 방향을 교대로 바꿈)

#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)

// 오름차순
// 패스 내부의 멈춤 도입 (스캔 범위 제한) & 패스의 스캔 방향을 교대로 바꿈
// 양방향 버블 정렬(셰이커 정렬)
void shaker(int a[], int n)
{
    int left = 0; // 위의 k의 역할 1(스캔 범위 조정)
    int right = n - 1; // 위의 k의 역할 2(스캔 범위 조정)
    int last = right; // 마지막으로 교환을 수행한 위치 저장(두 요소 가운데 오른쪽 요소). 마찬가지로 아무 교환이 수행되지 않으면 left = right = last이 되어 종료.

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

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