퀵정렬(Quick Sort)
퀵 정렬은 매우 빠른 속도를 보입니다.
퀵 정렬은 간단히 말해서 pivot을 정해서 low 와 high가 서로 교차 할 때 까지 교환하며 교차될 때 high를 pivot과 교체하고 전 pivot을 기준으로 반을 나눠서 왼쪽 영역과 오른쪽 영역에서 이 과정을 반복합니다.
그림으로 설명 드릴게요.
총 필요한 변수는 left, right, low, high, pivot 총 5개입니다.
우선 초기 세팅 결과는
초기 세팅
left 와 right는 각자 맨 왼쪽과 맨 오른쪽을 담당합니다.
pivot은 아무 기준으로 삼아도 되지만 우선 맨 왼쪽 5를 pivot으로 삼겠습니다.
low는 pivot을 제외한 맨 왼쪽을 담당하고 hight는 맨 오른쪽을 담당합니다.
low와 high의 이동
low와 high가 왼쪽 오른쪽으로 이동합니다.
이때 움직이는 기준은 아래와 같습니다.
-
low pivot보다 큰 값을 만날 때 까지
-
high pivot보다 작은 값을 만날 때 까지
low가 7을 만나고 high가 4를 만납니다.
이때 low와 high의 숫자를 교체합니다!!
아래는 교체 결과입니다!!
교체 완료
4와 7이 교체 된 것을 볼 수 있습니다.
또 다시 이동
또 다시 이동을 해서 low가 9를 high가 2를 가리킬 때 교체합니다.
그러면 low는 2를 가리키고 high는 9를 가리킵니다.
교차
high<low이므로 교차하였습니다. 이때는 서로 교체하지 않습니다.
low와 high의 이동이 완료됐습니다.
이떄 pivot과 high의 값을 바꾼다고 하였습니다.
pivot과 high의 값 교환
high와 pivot을 바꾼 결과입니다.
2는 맨 왼쪽으로 갔고 5는 제 위치를 찾았습니다.
5를 기준으로 왼쪽 오른쪽 영역 나누기
왼쪽 영역과 오른쪽 영역으로 나누어서 pivot을 다시 정하고 또 left와 right는 왼쪽과 오른쪽을 뜻하므로
left>right일 경우 교체할 필요가 없어집니다.
반복합니다 위의 과정을!!
위 과정들을 코드로 살펴봅시다!!
SWAP 함수
위의 함수는 말 그대로 교체함수입니다.
교체를 쉽게 하기 위해 정의했습니다.
low와 high의 이동과 교체
우선 pivot은 맨 왼쪽 숫자이기 때문에 pivot에 arr[left]의 값을 넣었습니다.
low는 피벗 제외 다음 숫자이기 때문에 left+1 값입니다.
high는 가장 오른쪽 숫자이기 때문에 right값입니다.
while문을 해석해보겠습니다.
low<=high라는 것은 서로 교차하기 직전입니다. 즉 교차하면 while문은 종료가 됩니다.
low를 이동시켜야 하기때문에 위에서 말한 조건인 low는 pivot보다 큰 값을 만날 때까지 이동합니다.
즉 pivot>arr[low]이면 피벗보다 작기 때문에 low를 이동시켜야 합니다.
low++는 오른쪽 이동입니다.
그다음 high를 이동시켜야 하는데 high는 위에서 말했듯이 pivot보다 작은 값을 만날 때까지 이동합니다.
pivot<arr[high]이면 피벗보다 크기때문에 계속 이동시킵니다.
high--는 왼쪽 이동입니다.
그리고 만약에 위 조건을 만족하여 교체할 상황이 온다면
if(low<=high)를 만납니다. 즉 교차되기 직전에 Swap함수를 통해 low와 high의 값을 교체합니다.
위의 최상위 while문이 끝나면(즉 교차가 됬다면)
Swap(arr,left,high)함수를 통해 pivot과 high가 가리키는 것을 교체합니다. left는 pivot을 가리키고 있기때문입니다.
이때 high 값을 반환을 하는데 이것은 pivot의 인덱스 위치정보를 반환 해줍니다.
이 값을 기준으로 나눠지게 됩니다 두 영역으로
퀵 정렬 부분
QuickSort함수에서는 위 Partition함수를 기준으로 퀵 정렬을 시도합니다.
pivot 변수에 Partition함수 반환값 피벗 위치를 받아 삽입합니다.
pivot 변수에는 pivot의 위치가 있습니다.
그걸 기준으로 재귀함수를 호출하여 왼쪽 영역 오른쪽 영역을 정렬합니다.
