[Algorithm] Bubble Sort (거품 정렬)

1. Bubble Sort (거품 정렬)

 

거품 정렬은 N개의 원소를 가진 배열을 정렬 시에 인접한 두 원소를 비교하여 정렬하는 방법이다. 시간복잡도는 크지만 구현이 간단하기 때문에 자주 사용된다.

 

크기 N의 배열을 정렬할 때, 인덱스 0번과 1번, 1번과 2번, ... N-2번과 N-1번의 원소들을 비교하여 자리를 교환해준다. 인접한 원소들의 교환을 한번 수행할 때마다 가장 오른쪽에 배치되는 원소는 올바르게 정렬되어진 값이 된다. 예를 들어 오름차순으로 정렬하는 경우 매 회차마다 가장 큰 수가 오른쪽으로 정렬되어진다. 이를 통해서 매 회차마다 가장 오른쪽으로 정렬된 값은 다음 회차의 정렬의 대상에서 제외된다.

 

 

2. Bubble Sort 구현

 

Bubble Sort는 첫 원소부터 N-i 까지의 원소에 대해서 인접한 원소와의 비교를 진행한다. 이때 i는 정렬을 실행한 횟수가 되는데 매 회차마다 올바르게 정렬된 부분은 제외하기 위해서 N-i로 구현한다.

 

- Java로 구현한 Bubble Sort

import java.util.Arrays;

import Algorithm.Sorting.Sort;

public class BubbleSort implements Sort {
    private int[] array;

    public BubbleSort(int[] array) {
        this.array = Arrays.copyOf(array, array.length);
    }

    @Override
    public int[] sort() {
        int N = array.length;
        for(int i = 0; i < N - 1; i++) {
            for(int j = 1; j < N - i; j++) {
                if(array[j] < array[j - 1]) {
                    int temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                }
            }
        }

        return array;
    }
}

 

 

3. Bubble Sort의 복잡도

- 시간 복잡도: O(N^2)

- 공간 복잡도: O(1)

 

 

[reference]

- https://www.geeksforgeeks.org/bubble-sort/

Bubble Sort - GeeksforGeeks

- https://ko.wikipedia.org/wiki/거품_정렬

거품 정렬 - 위키백과, 우리 모두의 백과사전