[알고리즘/Algorithm] 퀵 소트(Quick Sort)

QuickSort Quicksort는 Divide and Conquer 알고리즘으로, 어떤 원소를 기준점(Pivot)으로 고른 후 그 기준으로 어레이를 나누는 알고리즘이다. 우선 Psuedo Code로 간략하게 알고리즘에 대해 이해해보자. 우선 Partition의 목적은 A[p....i] 어레이는 모두 Pivot보다 작은 값으로. A[j...n] 어레이는 모두 Pivot보다 큰 값으로 만들고자 하는 것이다. 위 Psuedo Code를 하나하나 차례대로 뜯어보자. 우선 Pivot x를 A[p]값으로 설정한다. i는 p보다 하나 작은 값, j는 r보다 하나 큰 값으로 설정한다. r은 partition할 어레이의 맨 마지막 부분이다. 이렇게 하면 Pivot P를 기준으로 P의 오른쪽 부분에서 스위칭이 일어나게..

2019.10.29