CSKIM의 코딩로그/Python 알고리즘
[ Python ] 정렬 알고리즘 - 퀵정렬과 계수정렬
이전 글이었던 선택정렬과 삽입정렬에 이어 오늘은 퀵정렬과 계수정렬을 소개하고자 한다. 앞선 두 정렬은 정렬 알고리즘중에서는 속도가 느린편에 속한다. 물론 거의 정렬이 되어있는 리스트에서의 삽입정렬은 매우 효과적이지만 그것은 아주 제한적인 조건이며, 범용적으로는 느린편에 속하는 알고리즘이다. 그 중 퀵정렬은 앞선 두 알고리즘과 마찬가지로 빅-O 표기법에서의 시간복잡도는 O(N^2) 이다. 여기서 시간복잡도가 같은데 어떻게 더 효과적이라고 할 수 있는지에 대해서 짚고 넘어가자면, 빅-O 표기법은 최악의 경우에서의 시간복잡도를 나타낸다. 따라서 거의 정렬되어있는 경우에서의 삽입정렬이 O(N) 에 수렴하는 시간복잡도를 보여주기도 하지만, O(N^2) 로 나타내는 것이다. 퀵정렬도 마찬가지로 최악의 경우, 이미 ..
2021. 9. 29. 16:59
최근댓글