버블 정렬, 칵테일 정렬

버블 정렬

---

'버블 정렬'이라는 말은 액체 안의 공기 방울이 보글보글 위로 올라오는 모습에서 착안한 것이다. 이 알고리즘은 서로 인접한 두 원소를 비교하여 순서가 맞지 않으면 서로 교환하는 방식으로 정렬을 수행한다. 배열 요소 전체를 훑는 일련의 과정(비교, 교환작업)을 패스(pass)라고 한다. 한 패스가 끝나면, 배열의 가장 큰 원소 혹은 가장 작은 원소가 맨 끝으로 이동한다.
 버블 정렬의 시간 복잡도는 최악, 평균, 최선 모두 O(n^2)이다. 최악의 경우, 배열이 이미 정렬되어 있는 경우에도 교환 연산이 발생하므로 비효율적이다. 서로 이웃한 요소에 대해서만 교환하므로 이 정렬 알고리즘은 안정적이라고 할 수 있다.
 

기본적인 버블 정렬

// a[idx1] 와 a[idx2]의 값을 바꾼다.
static void swap(int[] a, int idx1, int idx2) {
    int tmp = a[idx1];
    a[idx1] = a[idx2];
    a[idx2] = tmp;
}

// 버블 정렬
static void bubbleSort(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        // 패스
        for (int j = n - 1; j > 0; j--) {
            if (a[j - 1] > a[j]) {
                swap(a, j - 1, j);
            }
        }
        // 패스 끝
    }
}

 
 

알고리즘 개선(1)

이전 패스에서 교환이 한 번도 이루어지지 않았다면 그 이전에 이미 정렬을 마쳤다는 뜻이다. 즉 4번째 패스의 교환 횟수가 0이라면 3번째 패스 때 이미 정렬된 상태라는 뜻이다. 이를 이용하면 불필요한 정렬 작업을 줄일 수 있다.

static void bubbleSort(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        int exchange = 0;
        // 패스
        for (int j = n - 1; j > 0; j--) {
            if (a[j - 1] > a[j]) {
                swap(a, j - 1, j);
                exchange++;
            }
        }
        // 패스 끝
        if (exchange == 0) break;
    }
}

 

 

알고리즘 개선(2)

패스 중에 특정 인덱스 이후로 교환이 수행되지 않는다면 그보다 앞쪽의 요소는 이미 정렬을 마친 상태라고 생각해도 좋다. 따라서 이후의 패스는 해당 인덱스 이후의 요소에 대해서만 비교, 교환을 수행하면 된다.

static void bubbleSort(int[] a) {
    int n = a.length;
    int k = 0;                          // a[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;                       // 패스가 끝나면 업데이트 한다.
    }
}

 
알고리즘을 개선하여도 시간 복잡도는 최선 O(n), 평균 O(n^2), 최악 O(n^2)이다.
 

 

칵테일 정렬

---

  '쉐이크 정렬', '양방향 버블 정렬'이라 불리기도 한다. 이 알고리즘은 버블 정렬의 변형으로서, 기본 아이디어는 양쪽 끝에서 시작하여 왼쪽으로 정렬하고, 그다음에는 오른쪽으로 정렬하는 것이다. 시간 복잡도는 최선 O(n), 평균 O(n^2), 최악 O(n^2)이다.

static void cocktailSort(int[] a) {
     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;  // 정렬된 오른쪽 인덱스 저장
    }
}