정렬

정렬 수행시간 정리

시간복잡도

<최악의 경우> (상한)
O(n^2) -> O(nlogn) -> O(n) -> O(logn) -> O(1) 순으로 빠름

CS50 강의 내용 정리
O(n^2) : 선택정렬, 버블정렬, 삽입정렬, 퀵정렬(평균시간복잡도는 O(nlogn))
O(nlogn) : 병합정렬
O(n) : 선형검색
O(logn) : 이진검색
O(1)

<최선의 경우> (하한)
Ω(n^2) : 선택정렬
Ω(nlogn) : 퀵정렬, 병합정렬
Ω(n) : 개선된버블정렬, 삽입정렬
Ω(logn)
Ω(1) : 선형검색, 이진검색 (한번에 찾은 경우)