퀵 정렬
- 기준 데이터를 설정, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.
- 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다.
- 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다. (e.g. C, Java, Python)
- 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)으로 설정한다.
동작 방식
빠른 이유
시간 복잡도
- 퀵 정렬은 평균의 경우 O(NlogN)의 시간 복잡도를 가진다.
- 하지만 최악의 경우, O(N^2)의 시간 복잡도를 가진다.
계수 정렬
- 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠르게 동작하는 정렬 알고리즘이다.
계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.
- 데이터의 개수가 N, 데이터(양수)중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N + K)를 보장한다.
동작 방식
시간 복잡도
- 계수 정렬의 시간 복잡도와 공간 복잡도는 모두 O(N + K)이다.
- 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다.
- 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있다.