본 문서는 다음 게시물에 많은 내용을 참고한다. 본 게시물은 피벗 sort를 이해하는데 참고하기에 좋다.

[알고리즘] 퀵 정렬 - Quick Sort (Python, Java)

추가 참고 자료

[Python] Quick sort. 파이썬에서 간단히 퀵 정렬 구현

퀵소트에 대한 자료를읽고 퀵 소트가 어떻게 동작하는지 잘 설명된 영상입니다.

https://www.youtube.com/watch?v=cWH49IKDIiI

퀵 정렬

퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 ****속한다.
분할 정복 알고리즘의 하나로, 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 합병 정렬과 달리 퀵 정렬은 리스트를 비균등하게 분활한다.
분할 정복 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. (분활 정복 방법은 대개 순환 호출을 이용하여 구현한다.

퀵 정렬 과정

리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot)이라고 한다.
피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다. 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.
피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다. 분활된 리스트에 대하여 순환 호출을 이용하여 정렬을 반복한다.
부분 리스트에서 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
부분 리스트들이 더 이상 분활이 불가능할 때까지 반복한다. 리스트의 크기가 0이나 1이 될 때까지 반복한다.

퀵 정렬 알고리즘의 구체적인 개념

하나의 리스트를 피벗을 기준으로 두 개의 비균등한 크기로 분할하고 분활된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된다. 리스트가 되게 하는 방법이다.