[CS50] 알고리즘 - 정렬 알고리즘의 실행시간

알고리즘 실행시간 비교

실행시간의 상한

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

 

실행시간의 하한 (개선 전)

• Ω(n²): 선택 정렬, 버블 정렬
• Ω(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

• 실행시간의 하한: Ω(n²)
• 문제: 이미 정렬되어 있어도 모든 비교를 수행

 

안쪽 루프에서 교환이 하나도 일어나지 않는다면 이미 정렬이 완료된 상태다.

따라서 바깥쪽 루프를 '교환이 일어나지 않을 때'까지만 수행하도록 변경한다.

 

개선된 의사 코드

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²): 선택 정렬
• Ω(n log n)
• Ω(n): 버블 정렬
• Ω(log n)
• Ω(1): 선형 검색, 이진 검색

 

연습 문제

Q. 선택 정렬의 실행 시간 하한도 버블 정렬처럼 더 단축시킬 수 있을까?
불가능하다.
선택 정렬은 정렬 상태와 관계없이 항상 Ω(n²)의 시간이 소요된다.

 

선택 정렬의 특성:

1. 매 단계에서 전체 배열을 탐색하여 최솟값을 찾음
2. 이미 정렬되어 있어도 최솟값을 찾는 과정은 생략할 수 없음
3. 교환 여부를 미리 알 수 없어 조기 종료 불가능

버블 정렬과의 차이:

• 버블 정렬: 교환 발생 여부로 정렬 완료를 판단 가능
• 선택 정렬: 최솟값 찾기는 항상 필요, 정렬 완료 여부와 무관

 

결론:
선택 정렬의 시간 복잡도는 최선/최악 모두 Θ(n²)이며, 개선이 불가능하다.