정렬 알고리즘의 실행시간

실행시간의 상한

O(n^2): 선택 정렬, 버블 정렬
O(n log n)
O(n): 선형 검색
O(log n): 이진 검색
O(1)

실행시간의 하한

Ω(n^2): 선택 정렬, 버블 정렬
Ω(n log n)
Ω(n)
Ω(log n)
Ω(1): 선형 검색, 이진 검색

여기서 버블 정렬을 좀 더 잘 할 수 있는 방법을 알아보겠습니다.

만약 정렬이 모두 되어 있는 숫자 리스트가 주어진다면 어떨까요?

원래 의사 코드는 아래와 같습니다.

Repeat n–1 times

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

여기서 안쪽 루프에서 만약 교환이 하나도 일어나지 않는다면 이미 정렬이 잘 되어 있는 상황일 것입니다.

따라서 바깥쪽 루프를 ‘교환이 일어나지 않을때’까지만 수행하도록 다음과 같이 바꿀 수 있습니다.

Repeat until no swaps

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

따라서 최종적으로 버블 정렬의 하한은 Ω(n)이 됩니다.

상황에 따라서는 선택 정렬보다 더 빠른 방법이 되는 것이죠.

실행시간의 하한

Ω(n^2): 선택 정렬
Ω(n log n)
Ω(n): 버블 정렬
Ω(log n)
Ω(1): 선형 검색, 이진 검색