Sort - Quick Sort (퀵정렬)

알고리즘 > 정렬 > 퀵정렬

기준 값을 중심으로 작은값은 왼쪽 큰 값은 오른쪽으로 분할하여 정렬하는 방식.

기준 값 (Pivot)값과 left, Right 값을 정하고 Left는 왼쪽에서부터 Pivot보다 큰값이 나올때까지 오른쪽으로 이동,

                                                             Right는 오른쪽에서부터 Pivot보다 작은 값이 나올때까지 왼쪽으로 이동.

두 값을 교환하며 이동하다가 Left와 Right 값이 만나면 Pivot과 교환.

제일 오른쪽 항목을 PIVOT으로 설정하고 LEFT를 왼쪽부터 오른쪽으로 RIGHT를 오른쪽부터 왼쪽으로 이동하면서 

PIVOT인 5보타 큰 LEFT 30으로 LEFT를 설정하고 5보다 작은 3을 RIGHT로 설정. 두 값을 교환한다. 

그리고 LEFT와 RIGHT를 계속해서 이동하여 만나는 값과 PIVOT값을 교환.

결과는 PIVOT과 교환한 값을 기준으로 왼쪽은 PIVOT보다 작은 값, 오른쪽은 PIVOT보다 큰 값으로 정렬된다. 

3은 비교할 값이 없으므로 고정되고 세번째 원소부터 마지막 원소까지 다시한번 PIVOT을 정하고 정렬을 시작한다. 

다시한번 17보다 큰 30이 LEFT, 17보다 작은 9가 RIGHT가 되고 두 원소가 바뀜.

그리고 LEFT와 RIGHT가 만나는 30과 PIVOT의 위치가 바뀌고 

정렬은 17을 기준으로 왼쪽인 11, 9 / 오른쪽인 28, 29, 35, 26, 30 으로 나뉨.

오른쪽 정렬을 다시 피벗을 기준으로 퀵정렬 실행. 

완료! 

n개의 원소에 대하여 n개의 메모리 사용

평균 시간 복잡도 :