버블 정렬

버블 정렬

시간 복잡도는 명령어가 몇 번 실행되는지 확인한다.

i for 문애서 (N - 1)

j for 문에서 (N - 1 - i) 개 만큼

이것은 전체 계산 값이 1이 될때까지 계속 되기 때문에 등차수열의 합으로 인해 N * (N -1) / 2, 

O(N^2) 의 최악의 시간복잡도를 가진다. 거의 못쓰는 수준.

 

void BubbleSort(vector<int>& v)
{
    const int n = (int)v.size();

    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n -i- 1; j++)
        {
            if (v[j] > v[j + 1])
            {
                int temp = v[j];
                v[j] = v[j + 1];
                v[j + 1] = temp;
                
            }
        }
    }
}