CSAlgorithm

[알고리즘] 버블정렬(Bubble Sort)

Algorithm, CS

버블정렬

1. 버블정렬의 개념

버블정렬은 인접한 두 개의 값을 비교하며 왼쪽 값이 오른쪽 값보다 크면 서로 위치를 바꾸는 방식이다.
그럼 7, 9, 5, 3, 1 을 오름차순으로 버블정렬해보자.

1 단계)

  1. 먼저 index 0 과 index 1 의 값을 비교한다. 7, 9, 5, 3, 1 에서 7과 9를 비교하면 되는데, 7은 9보다 작기 때문에 위치를 바꾸지 않는다.
  2. 그 다음, index 1 과 index 2 의 값을 비교한다. 7, 9, 5, 3, 1에서 9와 5를 비교했을 때, 왼쪽 값인 9가 더 크기 때문에 위치를 바꾼다.
  3. 그 다음, index 2 와 index 3 의 값을 비교한다. 7, 5, 9, 3, 1에서 9와 3를 비교했을 때, 왼쪽 값인 9가 더 크기 때문에 위치를 바꾼다.
  4. 그 다음, index 3 와 index 4 의 값을 비교한다. 7, 5, 3, 9, 1에서 9와 1를 비교했을 때, 왼쪽 값인 9가 더 크기 때문에 위치를 바꾼다.

1단계를 마치면 7, 5, 3, 1, 9로 정렬이 되고, 다섯 개의 수 중 가장 큰 수인 9가 가장 오른쪽에 위치하게 되었다. 버블정렬은 선택정렬과 달리 가장 마지막 index부터 정렬이 되는 방식이다. 1단계 정렬 과정은 아래와 같이 나타낼 수 있다.

7 9 5 3 1
7 9 5 3 1 => 7 5 9 3 1
7 5 9 3 1 => 7 5 3 9 1
7 5 3 9 1 => 7 5 3 1 9

1단계 정렬 결과 : 7 5 3 1 9

2 단계)

  1. 먼저 index 0 과 index 1 의 값을 비교한다. 1단계에서 정렬이 완료된 9를 제외한 나머지 네 개의 수 7, 5, 3, 1에서 7과 5를 비교했을 때, 왼쪽 값인 7이 더 크기 때문에 위치를 바꾼다.
  2. 그 다음, index 1 과 index 2 의 값을 비교한다. 5, 7, 3, 1에서 7과 3을 비교했을 때, 왼쪽 값인 7이 더 크기 때문에 위치를 바꾼다.
  3. 그 다음, index 2 과 index 3 의 값을 비교한다. 5, 3, 7, 1에서 7과 1을 비교했을 때, 왼쪽 값인 7이 더 크기 때문에 위치를 바꾼다.

2단계를 마치면 5, 3, 1, 7, 9로 정렬이 되고, 1단계에서 정렬이 완료된 9를 제외한 나머지 네 개의 수 중 가장 큰 수인 7이 가장 오른쪽에 위치하게 되었다. 2단계 정렬 과정은 아래와 같이 나타낼 수 있다.

7 5 3 1 9 => 5 7 3 1 9
5 7 3 1 9 => 5 3 7 1 9
5 3 7 1 9 => 5 3 1 7 9

2단계 정렬 결과 : 5 3 1 7 9

3 단계)

  1. 먼저 index 0 과 index 1 의 값을 비교한다. 1, 2단계에서 정렬이 완료된 7, 9를 제외한 나머지 세 개의 수 5, 3, 1에서 5와 3을 비교했을 때, 왼쪽 값인 5가 더 크기 때문에 위치를 바꾼다.
  2. 그 다음, index 1 과 index 2 의 값을 비교한다. 3, 5, 1에서 5와 1을 비교했을 때, 왼쪽 값인 5가 더 크기 때문에 위치를 바꾼다.

3단계를 마치면 3, 1, 5, 7, 9로 정렬이 되고, 1, 2단계에서 정렬이 완료된 7, 9를 제외한 나머지 세 개의 수 중 가장 큰 수인 5가 가장 오른쪽에 위치하게 되었다. 3단계 정렬 과정은 아래와 같이 나타낼 수 있다.

5 3 1 7 9 => 3 5 1 7 9
3 5 1 7 9 => 3 1 5 7 9

3단계 정렬 결과 : 3 1 5 7 9

4 단계)

  1. index 0 과 index 1 의 값을 비교한다. 1, 2, 3단계에서 정렬이 완료된 5, 7, 9를 제외한 나머지 두 개의 수 3, 1에서 3과 1을 비교했을 때, 왼쪽 값인 3이 더 크기 때문에 위치를 바꾼다.

4단계를 마치면 1, 3, 5, 7, 9로 정렬이 되고, 1, 2, 3단계에서 정렬이 완료된 5, 7, 9를 제외한 나머지 두 개의 수 중 가장 큰 수인 3이 가장 오른쪽에 위치하게 되었다. 4단계 정렬 과정은 아래와 같이 나타낼 수 있다.

3 1 5 7 9 => 1 3 5 7 9

4단계 정렬 결과 : 1 3 5 7 9

완료)

이 다음 단계는 할 필요가 없다. 남은 값이 1개이기 때문에 여기에서 정렬을 하는 것은 의미가 없기 때문이다. 따라서 아래와 같이 정렬이 완료되었다.

1 3 5 7 9


2. 버블정렬 시간복잡도

최선 평균 최악
O(n) O(n^2) O(n^2)


3. 버블정렬 JAVA 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 배열 a에서 i 위치와 j 위치의 값을 서로 바꾼다
static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

// 버블정렬
static void bubbleSort(int[] a) {
    for(int i=a.length-1; i>=1; i--) {
        boolean finished = true;
        for(int j=0; j<i; j++) {
            if(a[j] > a[j+1]) {
                swap(a, j, j+1);
                finished = false;
            }
        }
        if(finished) break;
    }
}

public static void main(String[] args) {
    int[] a = { 7, 9, 5, 3, 1 };
    bubbleSort(a);
    System.out.println(Arrays.toString(a)); // 출력결과 : [1, 3, 5, 7, 9]
}
Share