[정렬] 버블 정렬

버블 정렬이란?

버블 정렬은 무작위로 배치되어있는 요소들을 일정한 기준에 맞추어 정렬하는데 그 방법이 인접한 두 요소를 비교하여 의도한 순서가 될 때까지 교체하는 알고리즘입니다.

버블 정렬 과정

Cycle 1

Cycle 2

Cycle 3

Cycle 4

Cycle 5

Cycle 6

작업 순서

1. 첫 번째 인덱스부터 시작해서 두 요소를 비교한다.
2. 첫 번째 요소가 두 번째 요소보다 크면 서로 교체한다.
3. 이제 두 번째 요소와 세 번째 요소를 비교하여 교체가 필요한 경우 교체한다.
4. 마지막 요소까지 반복한다.

시간 복잡도

사이클을 돌 때마다 n, n-1, n-2, .... , 2, 1번 실행되게 되므로 시간 복잡도는 O(n^2)이다.

코드

이를 코드로 나타내면 다음과 같다.

public void bubbleSort(int[] array) {
        int n = array.length;

        // 배열의 모든 요소에 대해 반복
        for (int i = 0; i < n - 1; i++) {

            // 배열의 인접 요소 쌍을 비교
            for (int j = 0; j < n - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    // 요소가 잘못된 순서라면 교환
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }