정렬 알고리즘 #3. 버블 정렬 (Bubble Sort)

설명

버블 정렬은 연속된 두 개의 Index를 비교하여 정렬한 다음, 후 순위 숫자와 다음 Index를 다시 연속적으로 비교하여 정렬하는 방법이다

 

기본 로직

1. 두 번째 Index부터 시작한다
2. 현재 Index와 바로 이전의 Index 값을 비교한다
3. 이전 Index가 크면, 현재 Index와 값을 바꿔준다
4. 현재 Index가 크면, 다음 두 연속된 배열 값을 비교한다
5. (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 1 ~ 4 항목을 반복한다

시간복잡도

1부터 비교를 시작하여, n-1, n-2, ..., 1개를 반복하며, 전체를 대상으로 비교를 진행하므로 O(n^2)이다

 

코드

void BubbleSort(vector<int> v)
{
    for(int i = 0; i < v.size()-1; i++)
    {
        for(int j = 1; j < v.size()-1; j++)
        {
            if(v[j-1] > v[j])            
                swap(v[j-1], v[j]);
        }
    }
}