버블 정렬

버블 정렬이란?

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘으로 크기를 비교하여 순서대로 되어 있지 않으면 서로 교환하는 방식을 가진다.

동작 과정

1. 앞에서 부터 정렬할 것인지 뒤에서 부터 정렬할 것인지 정한다.
   1. 앞에서부터 정렬할 것이라면 뒤의 Index부터 비교하면서 앞의 Index로 와야 한다.
   2. 뒤에서부터 정렬할 것이라면 앞의 Index부터 비교하면서 뒤의 Index로 가야 한다.
2. 맨 뒤의 Index부터 인접한 두 요소를 비교하면서 Index 0까지 비교하면서 교환이 이루어 졌다면 0번째 요소는 정렬이 된 것이다.(해당 과정을 패스라고 일컫는다.) 다음은 맨 뒤의 Index부터 Index 1까지 비교한다. (즉, 0 ~ n - 1 요소 비교 → 1 ~ n - 1 요소 비교 … → n -2 ~ n - 1요소 비교)
3. 모든 교환이 이루어 졌을 경우 정렬이 완료된다.

개선점

사실 버블 정렬에는 코드내에서 개선 가능한 부분이 있다.

1. 어떤 패스에서 요소의 교환 횟수가 0이면 더이상 정렬할 요소가 없다는 뜻이기 때문에 정렬 작업(반복문)을 멈추면 됩니다.
2. 1번 방식보다 더 효과적인 방식은 객 패스에서 마지막으로 교환한 위치의 Index를 하나의 변수에 넣어놔주고 이후 수행할 패스의 범위를 제한할 수 있습니다.

1번의 경우 간단해 보이는데 2번의 경우 헷갈릴 수 있을 것 같으니 코드를 올려두도록 하겠습니다.

코드

void bubbleSortUpgrade(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] < a[j - 1]){
        swap(a, j - 1, j);
        last = j;
      }
    // 반복문이 끝났을 때 최종적으로 지점까지만 수행
    // 바뀌지 않은 앞의 Index는 이미 오름차순
    k = last;
  }
}

장단점

장점

1. 구현이 매우 간단하다.

단점

1. 순서에 맞지 않은 요소를 인접한 요소와 교환한다.

2. 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환이 되어야 한다.

3. 특히 특정 요소가 최종 정렬 위치에 있는 경우라도 교환되는 일이 일어난다.

시간 복잡도

비교 횟수를 봤을 때 n - 1회, n - 2회, … 이와 같은 방식으로 이루지므로 합계는 다음과 같다.

(n-1) + (n-2) + ... + 1 = n(n-1)/2

좀 더 정확히 구해보자면, 실제 요소를 교환하는 횟수는 배열의 요솟값에 더 많이 영향을 받기 때문에 교환 횟수의 평균값은 비교 횟수의 절반인 n(n-1) / 4 회입니다. 또한, swap 메소드 안에서 값의 이동이 3회 발생하므로 이동 횟수의 평균은 3n(n-1) / 4회 입니다.

---

Reference

• [알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog