버블정렬(Bubble sort) 개념/시간복잡도/Stable/In-place

버블정렬에 대한 이해

- 버블 정렬이란, 인접한 두 원소를 비교해 나가며 가장 큰 원소를 끝으로 보내는 과정을 N-1번 반복하는 알고리즘이다.

- 선택정렬과 유사하게, N-1번 부터 1번까지의 자리에 대하여 남아있는 수들 중 가장 큰 수를 각 자리로 보낸다.

- 이 때, 버블정렬은 남아있는 수들 중 가장 큰 수를 인접한 두 수를 비교해가며 찾는다.

 

 

N = 8인 다음과 같은 수열을 오름차순으로 정렬한다고 할 때,  7번째 자리에 위치해야 할 숫자는 인덱스 0번부터 7번까지에 있는 숫자들 중 가장 큰 숫자가 된다. 인접한 두 수를 비교해가며 가장 큰 수를 끝으로 보낸다. 

 

 

 

 

인덱스 0번과 1번에 있는 숫자를 비교하였을 때, 0번에 있는 숫자 3은 1번에 있는 숫자 7보다 작으므로 넘어간다.

 

 

 

 

이어서, 인덱스 1번에 있는 숫자 7은 인덱스 2번에 있는 숫자 2보다 크므로 두수의 자리를 바꾼다.

 

 

 

 

인덱스 2번에 있는 숫자 7은 인덱스 3번에 있는 숫자 1보다 크므로 두 수의 자리를 바꾼다. 

 

 

 

 

인덱스 3번에 있는 숫자 7은 인덱스 4번에 있는 숫자 6보다 크므로 두 수의 자리를 바꾼다.

 

 

 

 

인덱스 4번에 있는 숫자 7은 인덱스 5번에 있는 숫자 5보다 크므로 두 수의 자리를 바꾼다.

 

 

 

 

인덱스 5번에 있는 숫자 7은 인덱스 6번에 있는 숫자 4보다 크므로 두 수의 자리를 바꾼다.

 

 

 

 

마지막으로, 인덱스 6번에 있는 숫자 7은 인덱스 7번에 있는 숫자 0보다 크므로 두 수의 자리를 바꾼다.

이렇게 인접한 두 수를 비교하여 더 큰 수를 뒤로 보내는 과정을 한 사이클 반복하면, 남아있는 원소들 중 가장 큰 수가 끝 자리로 이동하게 된다. 이를 각 자리마다 반복하여 정렬을 완성한다.

 

 

 

 

코드

#include <iostream>
using namespace std;

int n = 8;
int arr[8] = {3, 7, 2, 1, 6, 5, 4, 0};

void bubbleSort(int st, int en) {

    for (int i=n-1; i>0; i--) { //i번째 자리로 남아있는 원소 중 가장 큰 원소 보내기
        for (int j=0; j<i; j++) {
            if (arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);
        }
    }   
}

void printarr() {

    for (int i=0; i<n; i++)
        cout<<arr[i]<<" ";
    cout<<endl;
}

int main() {

    bubbleSort(0, n);
    printarr();
    return 0;
}

/*0 1 2 3 4 5 6 7 */

 

 

 

버블 정렬의 시간복잡도

버블정렬은 외부 루프를 N-1번 도는 동안, N-1, N-2, N-3, ... , 1 번 인접한 원소들을 비교한다. 

따라서 T(n) = (n-1)+(n-2)+(n-3)+...+1 = (n-1)*n/2

O(n) = n^2 이다.

 

 

 

안정성 & 제자리성

버블정렬 알고리즘으로 정렬을 수행하는 경우, 동일한 값을 가지는 원소들의 본래 순서가 유지된다. 따라서 버블정렬은 안정정렬(Stable Sort)이다. 또한, 기존 배열 이외의 추가적인 메모리를 거의 사용하지 않는 제자리 정렬(In-place sort)이다.