Gwangyong Jeong

tyjk32@gmail.com

Backend Engineer

Updated:

1. 개요

버블 정렬(Bubble Sort)은 왼쪽 끝에서부터 시작해서 인접하는 두 항목의 값을 비교하여, 올바른 순서로 되어있지 않은 경우 두 값을 서로 교환하는 방식으로 정렬하는 방법을 말한다. 정렬의 과정이 마치 거품과 같다고 하여 버블 정렬(Bubble Sort)라고 불린다. 예제를 통해 버블 정렬(Bubble Sort)의 동작 방식에 대해 알아보도록 하자.

2. 예제

아래와 같이 5개의 값이 들어있는 배열을 오름차순으로 정렬해보도록 하자.

  1. 배열의 [0], [1]의 값을 비교하여 [0]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [0]의 값인 5가 [1]의 값인 4보다 크므로 자리가 바뀐다.

  2. 배열의 [1], [2]의 값을 비교하여 [1]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [1]의 값인 5가 [2]의 값인 1보다 크므로 자리가 바뀐다.

  3. 배열의 [2], [3]의 값을 비교하여 [2]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [2]의 값인 5가 [3]의 값인 3보다 크므로 자리가 바뀐다.

  4. 배열의 [3], [4]의 값을 비교하여 [3]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [3]의 값인 5가 [4]의 값인 2보다 크므로 자리가 바뀐다.

  5. 배열의 [4] 인덱스의 정렬이 완료되었다. 정렬 결과 가장 큰 값이 [4] 인덱스에 오게 되었다.

  6. 다시 처음으로 와서, 배열의 [0], [1]의 값을 비교하여 [0]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [0]의 값인 4가 [1]의 값인 1보다 크므로 자리가 바뀐다.

  7. 배열의 [1], [2]의 값을 비교하여 [1]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [1]의 값인 4가 [2]의 값인 3보다 크므로 자리가 바뀐다.

  8. 배열의 [2], [3]의 값을 비교하여 [2]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [2]의 값인 4가 [3]의 값인 2보다 크므로 자리가 바뀐다.

  9. 배열의 [3] 인덱스의 정렬이 완료되었다. 정렬 결과 두 번째로 큰 값이 [3] 인덱스에 오게 되었다.

  10. 다시 처음으로 와서, 배열의 [0], [1]의 값을 비교하여 [0]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [0]의 값인 1이 [1]의 값인 3보다 작으므로 자리가 바뀌지 않는다.

  11. 배열의 [1], [2]의 값을 비교하여 [1]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [1]의 값인 3이 [2]의 값인 2보다 크므로 자리가 바뀐다.

  12. 배열의 [2] 인덱스의 정렬이 완료되었다. 정렬 결과 세 번째로 큰 값이 [2] 인덱스에 오게 되었다.

  13. 다시 처음으로 와서, 배열의 [0], [1]의 값을 비교하여 [0]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [0]의 값인 1이 [1]의 값인 2보다 작으므로 자리가 바뀌지 않는다.

  14. 배열의 [1] 인덱스의 정렬이 완료되었다. 정렬 결과 네 번째로 큰 값이 [1] 인덱스에 오게 되었다.

  15. 배열의 [0] 인덱스의 정렬이 완료되었다. 정렬 결과 다섯 번째로 큰 값이 [0] 인덱스에 오게 되었다.

내림차순 정렬 시, 동일한 과정으로 비교해 나가며 앞의 값이 뒤의 값보다 작은 경우, 자리를 바꿔서 작은 수가 더 뒤에 위치하도록 정렬을 해나가면 된다.

3. 시간 복잡도

Best Average Worst
O(N^2) O(N^2) O(N^2)

N 번째 수 정렬 시 반복문 횟수 : N - 1

N-1 번째 수 정렬 시 반복문 횟수 : N - 2

…

두 번째 수 정렬 시 반복문 횟수 : 1

첫 번째 수 정렬 시 반복문 횟수 : 0

∴ 총 반복문 횟수 = n(n - 1) / 2

4. 구현 코드

4-1. C++

[소스 코드]

https://github.com/dev-aiden/problem-solving/blob/main/algorithm/bubbleSort.cpp

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include <iostream>
#include <vector>

using namespace std;

void bubbleSortAscending(vector<int> v) {
    int size = v.size() - 1;

    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size - i; ++j) {
            if (v[j] > v[j + 1]) {
                int temp = v[j];
                v[j] = v[j + 1];
                v[j + 1] = temp;
            }
        }
    }

    cout << "오름차순 정렬 후 : ";
    for (int i = 0; i < 5; ++i) cout << v[i] << " ";
    cout << '\n';
}

void bubbleSortDescending(vector<int> v) {
    int size = v.size() - 1;

    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size - i; ++j) {
            if (v[j] < v[j + 1]) {
                int temp = v[j];
                v[j] = v[j + 1];
                v[j + 1] = temp;
            }
        }
    }

    cout << "내림차순 정렬 후 : ";
    for (int i = 0; i < 5; ++i) cout << v[i] << " ";
    cout << '\n';
}

int main(void) {
    ios_base::sync_with_stdio(false);

    vector<int> v = { 5, 4, 1, 3, 2 };

    cout << "정렬 전 : ";
    for (int i = 0; i < 5; ++i) cout << v[i] << " ";
    cout << '\n';

    bubbleSortAscending(v);
    bubbleSortDescending(v);


    return 0;
}

[실행 결과]

4-2. JAVA

[소스 코드]

https://github.com/dev-aiden/problem-solving/blob/main/algorithm/bubbleSort.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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = {5, 4, 1, 3, 2};

        System.out.print("정렬 전 : ");
        for(int i = 0; i < 5; ++i) System.out.print(arr[i] + " ");
        System.out.println();

        bubbleSortAscending(arr);
        bubbleSortDescending(arr);
    }

    public static void bubbleSortAscending(int[] arr) {
        int[] arr2 = arr.clone();
        int size = arr2.length - 1;

        for(int i = 0; i < size; ++i) {
            for(int j = 0; j < size - i; ++j) {
                if(arr2[j] > arr2[j + 1]) {
                    int temp = arr2[j];
                    arr2[j] = arr2[j + 1];
                    arr2[j + 1] = temp;
                }
            }
        }

        System.out.print("오름차순 정렬 후 : ");
        for(int i = 0; i < 5; ++i) System.out.print(arr2[i] + " ");
        System.out.println();
    }

    public static void bubbleSortDescending(int[] arr) {
        int[] arr2 = arr.clone();
        int size = arr2.length - 1;

        for(int i = 0; i < size; ++i) {
            for(int j = 0; j < size - i; ++j) {
                if(arr2[j] < arr2[j + 1]) {
                    int temp = arr2[j];
                    arr2[j] = arr2[j + 1];
                    arr2[j + 1] = temp;
                }
            }
        }

        System.out.print("내림차순 정렬 후 : ");
        for(int i = 0; i < 5; ++i) System.out.print(arr2[i] + " ");
        System.out.println();
    }
}

[실행 결과]

Updated:

Leave a comment