[알고리즘] 퀵 정렬(Quick Sort)

분할-정복 알고리즘(주어진 문제의 입력 데이터를 작게 줄여서 문제를 분할하여 정복하는 방법)의 하나로 합병 정렬(Merge Sort)와 달리 리스트를 비균등하게 분할한다. 

① 리스트 안에 있는 한 요소를 선택한 후 이 원소를 '피벗(pivot)'이라고 하다

② 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽에 옮겨지고, 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.

③ 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.

     - 분할된 부분 리스트에 대하여 순환 호출을 이용하여 정렬을 반복한다.

     - 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.

④ 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다. (리스트의 크기가 0이나 1이 될때까지 반복한다.)

참고: https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog