퀵 정렬은 효율적인 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer)방식을 사용하는 알고리즘이다.
: 배열 내에서 하나의 원소를 “피벗”으로 선택한다.
피벗은 보통 첫 번째 원소, 마지막 원소, 중간 원소 또는 무작위로 선택할 수 있다.
피벗 전략에 따라 성능이 달라질 수 있다.
<aside> 📖
Info. 피벗이란? 피벗은 배열을 두 개의 부분 배열로 나누는 기준이 되는 원소를 말한다.
기준점 정렬해야 할 배열에서 하나의 값을 임의로 선택한 것이다. 이 선택된 피벗 값을 기준으로 배열의 다른 원소들을 나누다.
분할의 핵심 피벗보다 작거나 같은 값들은 피벗의 한쪽(보통 왼쪽)으로 모으고, 피벗보다 큰 값들은 피벗의 다른 쪽(보통 오른쪽)으로 모으는 방식으로 배열을 분할한다.
최종 위치 이 분할 과정이 끝나면, 피벗은 배열 내에서 자신의 최종 정렬 위치에 놓이게 ㅗ딘다. 이후에는 피벗의 왼쪽과 오른쪽에 있는 부분 배열만 다시 정렬하면 된다.
</aside>
: 피벗을 기준으로 배열을 두 개의 부분 배열로 나누다.
: 분할된 두 개의 부분 배열에 대해 다시 퀵 정렬을 재귀적으로 적용한다.