[알고리즘] 버블 정렬 (Bubble Sort, 개념과 장단점, 과정, 자바 코드 구현, 시간복잡도, 공간복잡도)

목차

• 버블 정렬이란?
• 버블 정렬 과정
• 버블 정렬 구현 (자바 코드)
• 시간복잡도
• 공간복잡도
• 정렬 알고리즘 비교

 

---

1. 버블 정렬이란?

연속하는 두 개의 원소를 오름차순 혹은 내림차순으로 비교하며 교환한다. 정렬되지 않는 값들 중 가장 큰 값(혹은 가장 작은 값)이 끝으로 이동하게 된다.

 

(특징)

• 최선, 평균, 최악의 시간복잡도는 모두 O(n^2)이다.
• 직관적이나 거의 사용하지 않는 정렬 알고리즘이다.

 

(장점)

• 알고리즘이 단순하고, 구현이 쉽다.
• 배열 내에서 교환하는 방식(제자리 정렬)으로 추가적인 메모리 공간을 필요로 하지 않는다.

(단점)

• 배열의 길이가 길어질수록 지수적으로 시간이 증가하기 때문에 비효율적이다.
• 하나의 요소가 끝으로 이동하기 위해서 배열의 모든 요소와 교환이 이뤄져야 한다.

 

---

2. 버블 정렬 과정

1) 연속하는 두 개의 요소를 비교한다.

 

    1-1) 첫번째 인덱스와 두번째 인덱스 값을 비교한다.

    1-2) 두번째 인덱스와 세번째 인덱스 값을 비교한다.

    1-3) 세번째 인덱스와 네번째 인덱스 값을 비교한다.

    1-n-1) n-1번째 인덱스와 n번째 인덱스 값을 비교한다.

 

2) 회차마다 정렬된 값이 맨 끝으로 이동하며, 정렬되지 않은 값들에 대해 (1)번 부터 반복한다.

 

 

---

3. 버블 정렬 구현 (자바 코드)

import java.util.*;
import java.io.*;

class Main {
    public static void main (String[] args) throws IOException {
        int[] arr = {5, 2, 2, 9, 100, 70, 11};
        int n = arr.length;

        // 오름차순 정렬
        int tmp;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n - i; j++) {
                if (arr[j-1] > arr[j]) {
                    tmp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }

        System.out.println(Arrays.toString(arr));
    }
}

 

---

4. 시간복잡도

데이터 개수가 n일 때,

• 첫번째 회차 비교 횟수 : 1 ~ (n-1) => n-1번
• 두번째 회차 비교 횟수 : 1 ~ (n-2) => n-2번
  ...
• n번째 회차 비교 횟수 : 1 => 1번

(n-1) + (n-2) + ... + 2 + 1 = n * (n-1) / 2 이다.

따라서 최선, 평균, 최악의 시간복잡도는 항상 O(n^2)이다.

 

---

5. 공간복잡도

데이터의 개수가 n일 때,

 

주어진 배열 내에서 교환이 이뤄지므로 공간복잡도는 O(n)이다.

 

---

6. 정렬 알고리즘 비교 (시간복잡도)