[버블 정렬 best case 시간복잡도] 진화한 버블 정렬, 완전히 정렬되었을 때 best case O(n)?

 

 

 

 

 

버블 정렬

---

학교에서 내부 정렬을 배울 때 가장 먼저 배우게 되는 정렬은 바로 버블 정렬입니다.

(내부 정렬이란 주기억 장치에서 이루어지는 정렬을 말합니다.)

왜냐하면 버블 정렬은 구현이 매우 간단하기 때문입니다.

 

 

하지만, 버블 정렬은 최종 정렬 위치에 있더라도 교환을 하는 일이 발생하는 등

굉장히 비효율적이기 때문에 자주 사용하지 않는다고 배웠습니다.

 

 

---

 

 

버블 정렬 시간 복잡도

---

하지만 버블 정렬의 시간 복잡도를 검색해보면

 

Worst case performance O(n²) 
Best case performance O(n) 
Average case performance O(n²) 

 

위와 같은 검색결과가 나옵니다.

최악의 경우와 평균은 O(n²)인데 최상의 경우가 O(n)으로 되어있습니다.

 

삽입 정렬의 경우는 완전히 정렬이 되어 있을 경우에 O(n) 시간 복잡도를 나타낸다고 배운 기억은 있는데,

버블 정렬은 Best case performance도 O(n²)으로 배웠던 것 같은데..

 

 

 

 

 

Best Case 시간 복잡도가 O(n²)인 버블 정렬

---

정답을 찾기 위해서 많은 블로그를 돌아다녔지만

제가 원하는 명확한 설명과 코드를 올린 블로그는 찾지 못했습니다.

'stackoverflow'에서 검색해보니 제가 원하는 결과를 찾았습니다!

 

 

제가 이해한 내용을 이렇습니다.
버블 정렬 알고리즘을 작성하는 방법은 여러 가지 있다고 합니다.

우리가 전에 알던 버블 정렬 알고리즘은 매우 비효율적이었지만

시간이 지나면서 버블 정렬 알고리즘이 효율적으로 변했다고 합니다. 

 

 

우리가 알던 버블 정렬은 아래와 같습니다.

아래 알고리즘의 최상/최악 시간 복잡도는 n²입니다.

---

기존에 우리가 알고 있던 버블 정렬 

---

BUBBLESORT(A)
for i = 1 to A.length - 1
    for j = A.length downto i + 1
          if A [j] < A[j - 1]
              exchange A[j] with A[j - 1]

 

---

 

 

 

Best Case 시간 복잡도가 O(n)인 버블 정렬

---

 

반면 Best Case 시간 복잡도가 O(n)인 버블 정렬은

숫자들이 바뀌었는지를 구분하는 'flag' 변수를 이용하여 개선이 되었습니다.

처음에 반복문이 돌면서 값을 비교하고 순서가 제대로 되어 있으면 바로 반복문을 빠져나옵니다.

그렇기 때문에 버블 정렬의 best case는 O(n^2)가 아닌 O(n)가 됩니다.

 

 

 

---

'flag'를 이용하여 swap 여부를 체크하고 swap이 되지 않았으면 반복문을 빠져나가는 개선된 버블 정렬 코드

---

 

    procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat 
        swapped = false
        for i = 1 to n-1 inclusive do
            /*순서가 올바른게 되어있는지 확인*/
            if A [i-1] > A [i] then
                /* swap 하고 swapped 변수를 'true'로 변경*/
                swap( A [i-1], A [i] )
                swapped = true
            end if
        end for
    until not swapped
end procedure

 

---

 

 

 

결론

---

이제는 버블 정렬의 best case 시간 복잡도가 O(n)이라는 말을 이해하게 되었습니다.

이 답을 얻기 위해서 정말 많은 글들을 읽었는데요.

블로그마다 설명이 다르게 되어 있어서 많이 혼란스러웠는데 정답을 찾은 것 같아 너무 뿌듯합니다.

이 글을 보신 분들에게도 이 글이 조금이나마 도움이 되었으면 좋겠습니다.

 

 

 

 

 

 

 

---

Reference

---

- StackOverFlow, "best-case-for-bubble-sort", https://stackoverflow.com/questions/1358383/best-case-for-bubble-sort, (2020.07.14)

- 위키백과, "거품 정렬", https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC, (2020.07.24)

 

---