퀵 정렬(Quick Sort)

quick sort

 

퀵정렬은 '피벗(pivot)'이라는 기준점을 두어 왼쪽서부터는 피벗보다 큰 원소를 고르고 오른쪽서부터는 피벗보다 작은 원소를 골라 교체해 나가는 원리이다.

이렇게 교체가 되면 어느순간 왼쪽서부터온 피벗보다 큰 원소와 오른쪽서부터온 피벗보다 작은원소의 위치가 뒤바뀌게 되는데 이를 기준으로 분할하여 다시 퀵정렬을 수행하게 된다.

 

*피벗(위키백과) : 선형대수학에서 피벗(pivot) 또는 피벗 성분(pivot entry,pivot element)는 특정 계산을 수행하기 위한 임의의 알고리즘 (예 : 가우스 소거법, 단순 알고리즘 등)에 의해 먼저 선택된 행렬의 성분(항,원소)이다.