정렬 알고리즘의 실행시간

학습 목표

여러 정렬 알고리즘과 검색 알고리즘의 실행 시간을 Big O와 Big Ω로 정의할 수 있다.

핵심 단어

• Big O
• Big Ω

---

지금까지 배운 선형 검색, 이진 검색, 버블 정렬, 선택 정렬의 실핼시간은 각각 어떻게 되는지 정리해보자.

실행시간의 상한

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