Computer Science - 정렬 알고리즘의 실행시간

여태까지 다뤘던 선형 검색, 이진 검색, 버블 정렬, 선택 정렬의 실행시간은

각각 어떻게 되는지 정리해 보자.

실행시간의 상한

• 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): 선형 검색, 이진 검색

Ref.
Edwith_boost course