[정렬] 버블 정렬(Bubble Sort)

- 서로 인접한 원소들끼리 비교하여 정렬 순서에 맞지 않으면 교환한다.

  => 최대 원소를 가장 뒤로 보내는 효과

- 이 최대 원소를 제외한 나머지 원소들을 같은 방법으로 교환한다.

  => 두 번째 최대 원소를 뒤에서 두 번째로 보내는 효과

- 이러한 작업을 반복한다.

 

 

다음은 버블 정렬 알고리즘이다.

bubbleSort(A[], n){
    for last ← downto 2{ // 1
        for i ← 1 to last - 1 // 2
            if(A[i] > A[i+1]) then A[i] ↔ A[i+1] 원소 교환 // 3
    }
}

- 1의 for 루프는 n-1번 반복한다.

- 2의 for 루프는 n-2, n-2,..., 2, 1번 반복한다.

- 3은 상수 시간 작업

 

따라서,

T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)

시간 복잡도는 O(n^2)이 된다.