퀵 정렬

• 퀵 정렬은 피벗을 기준으로하여 좌우를 나누기 때문에 파티션 교환 정렬 이라고도 불린다!
• 피벗은 기준을 의미하는 개념으로, 피벗보다 작으면 왼쪽, 크면 오른쪽과 같은 방식으로 파티셔닝을 하면서 쪼개 나간다.

퀵 정렬 의 원리

1. 기준이 되는 데이터를 피벗으로 설정한다. ( 가장 기본적인 퀵 정렬은 첫 번재 데이터를 기 데이터(Pivot)로 설정한다!)
2. 피벗을 설정 한 후, 피벗을 기준으로 왼쪽에는 피벗보다 큰 데이터를 찾고, 오른쪽에서는 피벗보다 작은 데이터를 찾아서 서로 위치를 교환한다.
3. 1,2 과정을 반복!

로직

1. [6, 5, 1, 4, 7, 2, 3]

• 퀵 정렬은 Pivot이라고 불리는 임의의 기준값을 사용한다 Pivot값을 선택하는데는 여러 가지 방법이 있지만 간단한 설명을 위해 중앙에 위치한 4를 Pivot으로 정한다

2. [3, 2, 1] < 4(pivot) < [7, 5, 6]

• 위와 같이 pivot 값보다 작은 값들은 모두 왼편으로 몰고, 큰 값들은 모두 오른편으로 몰면 기준값은 정확히 정렬된 위치에 놓이게 된다. 이런 방식으로 분할을 해놓으면 앞으로 더 이상 왼편에 있는 값들과 오른편에 있는 값들 간에는 비교를 할 필요가 없다. 따라서 반대편은 전혀 신경쓰지 않고 왼편이든 오른편이든 같은편 내의 값들 끼리만 비교 후 정렬을 할 수 있게 된다.

1. [1] < 2(pivot) < [3]

• 왼편의 정 가운데에 위치한 pivot 값인 2 보다 작은 값인 1 은 왼쪽에 큰 값인 3은 오른쪽에 위치시킨다. 이제 양쪽 모두 값이 하나씩 밖에 없기 때문에 이로써 왼편의 정렬 작업은 완료!

1. [ ] < 5(pivot) < [7, 6]

• 오른편의 pivot값인 5보다 작은 은 없으므로 7 과 6을 모두 오른편에 위치시킨다.