[Algorithm] Bubble Sort (거품 정렬)

[Algorithm] Bubble Sort (거품 정렬)

 

1. 정의

• 서로 인접한 두 원소의 대소를 비교하고, 더 큰 원소를 뒤로 보내서 정렬하는 알고리즘
• 시간 복잡도
  • 최선 : $O(n^2)$
  • 평균 : $O(n^2)$
  • 최악 : $O(n^2)$

2. 동작 과정

1. 첫 번째 원소와 두 번째 원소의 대소를 비교하여 첫 번째 원소가 더 크다면 두 원소의 위치를 바꾼다.
2. 두 번째 원소와 세 번째 원소의 대소를 비교하여 두 번째 원소가 더 크다면 두 원소의 위치를 바꾼다.

​ ...

n - 1. (n - 1) 번째 원소와 n 번째 원소의 대소를 비교하여 (n - 1) 번째 원소가 더 크다면 두원소의 위치를 바꾼다.

→ 이런식으로 탐색 시작 범위를 하나씩 증가시키며 정렬을 진행한다.

3. 장단점

• 장점
  • 구현이 매우 간단, 소스가 직관적
  • 안정 정렬(Stable Sort)
  • 제자리 정렬(in - place sorting)
• 단점
  • 비효율적

4. 코드 (오름차순)

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

void swap(int[] arr, int first, int second) {
  int tmp = arr[second];
  arr[second] = arr[first];
  arr[first] = tmp;
}

---

※ 참고

• tect-refrigerator 거품 정렬(Bubble Sort)
• 정렬 알고리즘 6개 정리 - Jinhyy
• [알고리즘] 버블 정렬 알고리즘 (Bubble Sort)