[Algorithm] 버블 정렬(Bubble Sort)

1. 버블 정렬이란?

• 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘으로 단순 교환 정렬(straight exchange sort)라고도 한다.
• 시간 복잡도는 O(n^2)로 효율이 좋지 않다.

이미지 출처: https://www.productplan.com/uploads/bubble-sort-1024x683-2.png

정렬 과정

1. 배열의 끝에 있는 두 요소부터 비교를 시작한다.

2. 이웃한 두개의 요소를 비교하고 왼쪽 요소가 오른쪽 요소보다 작으면 위치를 교환한다.

3. 위의 과정을 첫번째 요소까지 반복한다. (이 과정을 패스, pass 라고 한다)

 

2. 버블 정렬 구현

public void swap(int[] arr, int idx1, int idx2) {
  int t = arr[idx1];
  arr[idx1] = idx2;
  arr[idx2] = t;
}

public void bubbleSort(int arr) {
  for(int i = 0; i < arr.length - 1; i++) {
    int exchange = 0; // 패스에서 교환하는 횟수
    
    for(int j = arr.length - 1; i > i; j--) {
      if(arr[j - 1] > arr[j]) {
        swap(arr, j - 1, j);
        exchange++;
      }
      if(exchange == 0) break; // 교환이 이루어지지 않으므로 멈춤
    }
  }
}

 

3. 알고리즘 개선

• 각 패스에서 교환을 하다가 어떤 시점 이후에 교환을 하지 않는다면 그보다 앞의 요소는 이미 정렬을 마친 상태이다.
• 따라서 교환할 때마다 오른쪽 요소의 인덱스를 last값에 저장한다.
• 하나의 패스를 마쳤을 때 last값을 k에 대입하여 다음에 수행할 패스의 범위를 제한하여 비교 횟수를 줄인다.

public void swap(int[] arr, int idx1, int idx2) {
  int t = arr[idx1];
  arr[idx1] = idx2;
  arr[idx2] = t;
}

public void bubbleSort(int arr) {
  int k = 0; // arr[k]보다 앞은 정렬을 마친 상태
  
  while (k < arr.length - 1) {
    int last = arr.length - 1; // 마지막으로 요소를 교환한 위치
    
    for(int j = arr.length - 1; j > k; j--) {
      if(arr[j -1] > arr[j]) {
        swap(arr, j - 1, j);
        last = j;
      }
      k = last;
    }
  }
}