[Algorithm] 5-(2). 정렬 - 퀵 정렬

[Algorithm] 5-(2). 정렬 - 퀵 정렬

 

 

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. 일반적 상황에서 가장 많이 사용된다.

 

병합 정렬과 더불어 대부분 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이며, 가장 기본적 퀵 정렬은 첫 번째 데이터를 기준 데이터(피봇)로 설정한다.

 

피봇값 설정 -> 정렬 -> 분할 -> 왼쪽 데이터 퀵정렬 -> 오른쪽 데이터 퀵정렬

 

5 7 9 0 3 1 6 2 4 8

 

첫번째 원소가 피봇으로 설정된다.

 

 

이상적인 경우 시간 복잡도가 O(NlogN)이 될 수 있다. 데이터 확인 개수가 절반씩 줄어들기 때문이다. 그러나, 최악의 경우 O(n2)의 시간 복잡도를 가진다.