버블 정렬(bubble sort)

• 이웃한 두 요소의 대소 관계를 비교/교환을 반복하여 최종적으로 배열을 정렬시키는 알고리즘

6

4

3

7

1

9

8

1. 먼저 오른쪽 끝에 있는 두 요소부터 비교/교환한다. 오름차순으로 정렬한다면 왼쪽 요소 값이 오른쪽 요소 값보다 클 때 교환한다.
2. 그 다음 오른쪽에서 2, 3번째 요소를 비교/교환한다. 이 작업을 첫 번째 요소까지 반복한다.

• 길이가 n인 배열에서 n - 1회 비교/교환을 하면 가장 작은 요소가 왼쪽 끝으로 이동한다. 
• 이런 하나의 사이클을 패스(pass)라고 하며, 첫 번째 패스가 끝나면 두 번째 패스는 왼쪽 끝으로 이동한 요소를 제외한 배열에 대해 비교/교환을 한다.
• 두 번째 패스의 비교 횟수는 첫 번째 패스보다 정렬한 요소가 하나 줄었기 때문에 1회 적은 n - 2회이다.
• 모든 정렬이 끝나려면 n - 1회의 패스가 수행되어야 한다.
• 시간 복잡도는 O(n^2)

버블 정렬 프로그램

• n - 1회의 패스를 수행한다.
• 각 패스는 이웃한 두 요소(j - 1, j)를 오른쪽 → 왼쪽으로 비교/교환하며 스캔한다.
• 오른쪽부터 스캔하므로 j(오른쪽 요소의 인덱스)의 시작값은 n - 1 이고 i + 1이 될 때까지 감소한다.

// a[idx1]와 a[idx2]의 값을 바꿉니다. 
static void swap(int[] a, int idx1, int idx2) {
    int t = a[idx1]; 
    a[idx1] = a[idx2]; 
    a[idx2] = t;
}
 
//버블 정렬(버전 1)
static void bubbleSort(int[] a, int 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);
}

 

• 만약 어떤 패스에서 정렬을 마치게 되면 그 다음 패스부터는 요소 교환이 이루어지지 않는다.
• 즉, 어떤 패스에서 요소 교환 횟수가 0이되면 더 이상 정렬할 요소가 없다는 뜻이므로 정렬 작업을 멈춘다.

//버블 정렬(버전 2)
static void bubbleSort(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 - 1, j);
                exchg++;
            }
        if (exchg == 0) break;                    // 교환이 이루어지지 않으면 종료합니다.
    }
}

 

• 만약 패스에서 비교/교환을 하다가 어떤 요소 이후로는 교환이 수행되지 않는다면 그 앞쪽의 요소는 이미 정렬을 마친 상태라고 생각해도 좋다.
• 따라서 다음 패스는 마지막으로 교환한 요소까지 비교/교환을 수행하면 된다.

//버블 정렬(버전 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--) {
            if (a[j - 1] > a[j]) {
                swap(a, j - 1, j);
                last = j;
            }
        }
        k = last;
    }
}

 

양방향 버블 정렬(bidirection bubble sort) / 칵테일 정렬(cocktail sort) / 셰이커 정렬(shaker sort)

• 홀수 번째의 패스는 가장 작은 요소를 맨 앞으로 옮기고 짝수 번째의 패스는 가장 큰 요소를 맨 뒤로 옮기는 방식(패스의 스캔 방향을 교대로 바꾼다)

//양방향 버블 정렬 / 칵테일 정렬 / 셰이커 정렬
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;
    }
}