개념
퀵 정렬은 평균적으로 가장 빠른 실행속도를 지닌 알고리즘이다.
분할정복 알고리즘을 기반으로하며, 다음과 같은 과정을 거친다.
- 리스트 안에 있는 원소(Pivot) 중 택 일
- Pivot을 기준으로 pivot보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 옮긴다.
- 피봇을 제외한 왼쪽 리스트와 오른쪽 리스트에 대해서 다시 정렬 해줌.
- 분할된 부분 리스트에 대해서 이 과정을 반복 수행함.
코드
우선, 해당 리스트의 길이가 1개 이하이면 해당 리스트 리턴.
그렇지 않다면,
pivot을 최초의 리스트의 첫번째 요소로 지정.
tail은 pivot 뒤에 존재하는 모든 요소들로 지정.
해당 피봇을 기준으로 리스트 내 값이 작은 아이들을 left, 큰 아이들을 right.
해당 과정을 계속 해서 반복.
결과
시간복잡도
일반적으로 예측되는 평군되는 상황은 pivot을 기준으로 왼쪽,오른쪽 사이드가 각각 반 반 씩 나눠지는 상황이다.
그러면 logN 만큼의 단계로 나눠 질 수 있다.
그리고 왼쪽,오른쪽으로 나눠진 사이드의 값의 비교는 n개의 숫자만큼 비교해야 하므로 n의 시간복잡도가 나오는 걸 알 수있다.
(물론 이 나눠진 숫자들이 또 다시 나눠질 때의 시간복잡도는 n/2가 될 것이다.)
그래서 결과적으로 O(nlogN) 의 시간복잡도를 가지게 된다.
단,
최악의 경우에는.
위의 그림과 같이 pivot의 숫자가 항상 가장 작은 숫자이면 pivot과 나머지 숫자와의 비교 연산을 n번만큼의 수행해야하고 그 단계가 리스트 내 숫자만큼의 n단계 만큼 존재할지니 O(N^2)의 시간복잡도가 생성된다.
WILL is ALL