버블 정렬(Bubble Sort)

- 버블 정렬은 해당 작업을 반복한다

1. 바로 다음 차수와 비교한다

2. 다음 차수보다 현재 차수가 크다면 교환

(교환이 없다면 이미 정렬이 되어있는 상태)

 

반복 과정에서 정렬되는 순서를 직관적으로 알 수 있으며

선택 정렬과 같이 쉽고 간단한 구현도라서 좋아하는 방법이다

교환 여부로 정렬 완료 시점을 알 수 있어 최적화도 가능하다

 

 

- 자바로 간단한 예제를 짜고 주석을 달아놓고

//n개 입력 값을 받음(입력 값을 모른다는 가정)
int[] array = new int[n];

//교환 여부
boolean flag = true;

//교환이 없을 경우 종료
for(int sortIdx = 0; flag; sortIdx++) {
    flag = false;
    
    //교환을 위한 입력 값 순환
    for(int compareIdx = 0; compareIdx < array.length - sortIdx - 1; compareIdx++) {
        //인접 값 비교(이미 정렬된 값 생략)
        if(array[compareIdx] > array[compareIdx + 1]) {
            //XOR 값 교환
            array[compareIdx] = array[compareIdx] ^ array[compareIdx + 1];
            array[compareIdx + 1] = array[compareIdx] ^ array[compareIdx + 1];
            array[compareIdx] = array[compareIdx] ^ array[compareIdx + 1];
            
            flag = true;
        }
    }
}

//결과 출력
System.out.println(Arrays.toString(array));

 

 

- 마지막으로 시간 복잡도(Big-O)에 대해 말하자면

외부 반복문은 교환이 없을 경우 종료로
정확한 횟수를 구할 수 없고

최악의 경우 n-1번 실행한다고 가정

여기서 상수는 무시함으로

n-1
-> O(n)

 

내부 반복문을 계산 할 경우

반복이 진행될수록 점점 줄어들어

기존 중첩 반복문으로 정확한 계산이 불가하다

ex) O(n) * O(n) = O(n^2)

 

하지만 전체 횟수를 등차수열의 합으로 표현할 수 있으며

ex) (n - 1) + (n - 2) + ... + 2 + 1

 

예를 들어 배열이 다섯개가 주어진 경우

(5 - 1) + (5 - 2) + (5 - 3) + (5 - 4) = 10

 

여기서 등차수열의 합 공식을 풀이하고

항의 개수 / 2 * (첫 번째 값 + 마지막 값)

-> n - 1 / 2 * ((n - 1) + 1)

-> n - 1 / 2 * (n - 1 + 1)

-> n - 1 / 2 * n

-> n(n - 1) / 2

 

등차수열의 합으로 계산을 한다면

5(5 - 1) / 2

-> 20 / 2

-> 10

 

다음 빅오 표기법을 적용하면

1. 상수 계수 무시(분모 포함)

2. 가장 큰 차수만 남김

n(n - 1) / 2

-> n^2 / 2 - n / 2

-> O(n^2)

 

마지막으로 외부 반복문과 내부 반복문을 합하지만

여태까지 말했던 상수와 작은 차수를 제외하면

O(n) + O(n^2)

-> O(n^2)

 

특이 사항으로 최선(최적) 예를 들어 이미 정렬이 돼있다면

O(n)을 가지지만 시간 복잡도는 최악인 경우를 상정하여

 

버블 정렬은 O(n^2)의 시간 복잡도를 가진다