2021.2.21 TIL : [자료구조] 퀵 정렬(Quick Sort)

퀵 정렬은 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법이다. 값을 서로 교체하는 데에 N번, 엇갈린 경우에 교체 이후에 원소가 반으로 나누어지므로 전체 원소를 나누는 데에 평균적으로 log N번이 소요 되므로 평균적으로 Θ(N log N)의 시간 복잡도를 가진다.

*'피벗'은 뭔가요?

피벗은 특정 계산을 수행하기 위한 임의의 알고리즘에 의해 먼저 선택된 행렬의 성분(항, 원소)이다.

 

퀵 정렬은 편향된 분할(정렬할 데이터가 이미 정렬이 되어 있거나 역으로 정렬되어 있는 경우 - 피벗이 한 쪽으로 치우쳐 N개의 원소를 피봇 기준으로 나누는 작업을 N번 실행)이 발생할 때 연산의 양이 O(N^2)이다. 따라서 실제로 정렬을 함에 있어서는 퀵 정렬을 직접 구현하지 않는다. 따라서 C++의 Algorithm이라는 라이브러리를 사용하기도 한다. Algorithm 라이브러리의 sort()함수는 퀵 정렬을 기반으로 하되 O(N log N)을 보장한다. 

 

퀵정렬을 C언어로 구현한 코드는 여기에서 확인할 수 있다.