버블정렬

2019-12-31

끝의 요소부터 두개씩 비교하여 정렬하는 방식이다.

n + (n-1) + (n-2) + ... + 1 = n(n-1)/2번의 비교가 일어난다.

코드는 다음과 같다.

static void bubbleSort(int[] arr) {
    int len = arr.length;
    for (int i = 0; i < len - 1; i++) {
      for (int j = len - 1; j > i; j--) {
        if (arr[j - 1] > arr[j]) {
          swap(arr, j - 1, j);
        }
      }
    }
}

static void swap(int[] arr, int idx1, int idx2) {
    int tmp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = tmp;
}

여기서 교환횟수를 측정하면 알고리즘을 개선할 수 있다. 이 전의 패스에서 교환횟수가 0이면 그 이후에서도 교환이 일어나지 않을 것을 알 수 있으므로 반복문을 끝내면 된다.

static void bubbleSort(int[] arr) {
    int len = arr.length;
    for (int i = 0; i < len - 1; i++) {
      int chg = 0;
      for (int j = len - 1; j > i; j--) {
        if (arr[j - 1] > arr[j]) {
          swap(arr, j - 1, j);
          chg++;
        }
      }
      if(chg == 0) break;
    }
}

여기서 마지막 교환 인덱스를 활용하면 알고리즘을 더 개선할 수 있다. 예를들어 {1,2,5,4,3}의 경우, 처음 루프실행 때 2번 인덱스에서 마지막 교환이 일어난 후엔 교환이 더이상 일어나지 않는다. 이 경우엔 다음엔 3번 인덱스까지만 비교하면 된다.

static void bubbleSort(int[] arr) {
  int len = arr.length;
  int k = 0;									// arr[k] 이전은 정렬이 되어있는 상태
  while (k < len - 1) {
    int last = len - 1;
    for (int j = len - 1; j > k; j--) {
      if (arr[j - 1] > arr[j]) {
        swap(arr, j - 1, j);
        last = j;
      }
    }
    k = last;
  }
}

마지막으로, {5,1,2,3,4} 배열의 경우, 위의 알고리즘은 빠른시간안에 정렬을 마칠 수 없다. 왜냐하면 맨 앞의 5는 한번의 루프에 한번씩만 뒤로가기 때문이다. 따라서 홀수번째 패스때는 가장 작은 요소를 맨 앞으로 옮기고 짝수번째 패스때는 가장 큰 요소를 뒤로 옮기면 적은 비교로 정렬을 할 수 있다. 이런 방식을 양방향 버블 정렬이라고 한다.

static void bubbleSort4(int[] arr) {
  int last = arr.length - 1;
  int first = 0;
  int turn = 0;
  while (first < last) {
    if (turn % 2 == 0) {
      for (int j = first + 1; j < last; j++) {
        if (arr[j - 1] > arr[j]) {
          swap(arr, j - 1, j);
        }
      }
      last--;
    } else {
      for (int j = last; j > first; j--) {
        if (arr[j - 1] > arr[j]) {
          swap(arr, j - 1, j);
        }
      }
      first++;
    }
    turn++;
  }
}

Loading script...