[SORT] Bubble Sort (버블 소트)

Goal

정렬 알고리즘 중 Bubble Sort 에 대해 알기
Bubble Sort의 장· 단점
시간 복잡도 이해하기
자바로 구현할 줄 알기

Bubble Sort (버블 소트) 알고리즘

두개의 값을 계속 비교해 나아가면서 값을 정렬시키는 알고리즘이다.

아래 예시를 통해 이해해 보자

PASS 1: 왼쪽 값과 오른쪽 값을 비교한다.

• 왼쪽 값이 오른쪽 값보다 더 크다면, 두 개의 값을 바꾼다.

PASS 2: 다시 배열의 처음으로 가서 이를 계속 반복한다.

---

Bubble Sort (버블 소트) 의 장 · 단점

장점 :

• 구현이 단순하다.

단점 :

• 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열의 모든 요소들과 교환이 이루어져야한다.
• 교환하는 것보다 이동 작업이 더 많기 때문에 거의 쓰이지 않는다.

Bubble Sort (버블 소트) 의 시간복잡도

데이터가 n 개일 때 걸리는 시간 복잡도는 O(n^2) 입니다.

• 데이터 개수 n 개일 때
  • 전체 합 : (n-1) + (n-2) + (n-3) + ..... + 2 + 1 => n(n-1) / 2

Bubble Sort (버블 소트) JAVA 구현

public class BubbleSort {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.valueOf(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.valueOf(br.readLine());
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            sb.append("PASS " + (i + 1) + " : ");
            for (int k = 0; k < n; k++) {
                sb.append(arr[k] + " ");
            }
            sb.append("\n");
        }
        for (int i = 0; i < n; i++) {
            sb.append(arr[i] + " ");
        }
        System.out.println(sb);
    }
}

윗 예시를 코드를 통해 똑같이 적용.

n = 6, array = [5, 10, 8, 6, 1, 3]