Sort Algorithm - Quick

Quick

- Divide & Conquer Algorithm 중 하나

 

- pivot을 이용 - 위치에 따라 간격의 불균형이 발생할 수도 있다.

 

- Merge Sort와 속도가 비슷하고, Heap Sort보다 속도가 빠르다.

---

Java예시

*left = 부분 Array의 1st index

*pivot = 부분 Array의 중간값

*right = 부분 Array의 last index

partition() :

- left<=right가 될 때까지, left의 element값이 pivot보다 클 때까지 증가시키면서, right 의 element값이 pivot보다 작을 때까지 감소시키면서 찾는다.

 

- 위 조건을 만족하는 value를 찾으면, 두 elements를 swap한다.

(이 과정을 진행하다보면, 자연스럽게 오름차순으로 정렬된다.)

 

- 찾는과정이 다 끝나면, pivot의 위치인 left를 return한다.

quickSort() : return 받은 pivot을 기준으로 좌/우 부분집합으로 나누어 재귀호출을 진행

 

sortByQuickSort() : Quick Sort Algorithm실행

 

 

- main함수에서 실행한 결과

---

C예시

 

- 추가 예정