버블 정렬(Bubble sort) 시간 복잡도 O(n^2)

버블 정렬 (Bubble Sort)

순서대로 근접한 두 수(연속된 두개 인덱스)를 비교하여 정한 기준의 값을 뒤로 넘겨 정렬하는 방법

오름차순으로 정렬하고자 할 경우, 비교시마다 큰 값이 뒤로 이동하여 1바퀴 돌 시 가장 큰 값이 맨 뒤에 저장됨

맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장되기 때문에 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복

 

기본 로직

1. 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스 값과 바로 이전의 인덱스 값을 비교한다.
2. 만약 이전 인덱스가 더 크면 현재 인덱스와 바꿔준다.
3. 현재 인덱스가 더 크면 교환하지 않고 다음 두 연속된 배열 값을 비교한다.
4. 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼만 반복한다.

 

 

장점

구현이 매우 간단하다.

단점

순서에 맞지 않은 요소를 인접한 요소와 교환한다.
하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.

 

복잡도

이 정렬 알고리즘은 1부터 비교를 시작하여 n-1개 n-2개 ... 1 개씩 비교를 반복하며

선택 정렬과 같이 배열이 어떻게 되어있던지 간에 전체 비교를 진행하므로 시간 복잡도는 O(n^2)이다.

공간복잡도도 이 또한 단 하나의 배열에서만 진행하므로 O(n)이다.

 

JAVA 구현

for(int i = 0 ; i < n - 1 ; i ++) {
    boolean change = false;
    for(int j = 0 ; j < n - 1 - i ; j ++){
        if(arr[j] > arr[j + 1]) {
            change = true;
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
    if(change == false) break;
}