퀵 정렬(Quick Sort) 이란?

퀵 정렬은 효율적인 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer)방식을 사용하는 알고리즘이다.

작동 방식

  1. 피벗(Pivot) 선택

: 배열 내에서 하나의 원소를 “피벗”으로 선택한다.

피벗은 보통 첫 번째 원소, 마지막 원소, 중간 원소 또는 무작위로 선택할 수 있다.

피벗 전략에 따라 성능이 달라질 수 있다.

<aside> 📖

Info. 피벗이란? 피벗은 배열을 두 개의 부분 배열로 나누는 기준이 되는 원소를 말한다.

  1. 기준점 정렬해야 할 배열에서 하나의 값을 임의로 선택한 것이다. 이 선택된 피벗 값을 기준으로 배열의 다른 원소들을 나누다.

  2. 분할의 핵심 피벗보다 작거나 같은 값들은 피벗의 한쪽(보통 왼쪽)으로 모으고, 피벗보다 큰 값들은 피벗의 다른 쪽(보통 오른쪽)으로 모으는 방식으로 배열을 분할한다.

  3. 최종 위치 이 분할 과정이 끝나면, 피벗은 배열 내에서 자신의 최종 정렬 위치에 놓이게 ㅗ딘다. 이후에는 피벗의 왼쪽과 오른쪽에 있는 부분 배열만 다시 정렬하면 된다.

</aside>

  1. 분할(Parition)

: 피벗을 기준으로 배열을 두 개의 부분 배열로 나누다.

  1. 재귀(Recursion)

: 분할된 두 개의 부분 배열에 대해 다시 퀵 정렬을 재귀적으로 적용한다.