📚 목차

요약

1. 퀵 정렬

1. 퀵 정렬

• 기준값 pivot을 선정하여 해당 값보다 큰 데이터와 작은 데이터로 분류하는 과정을 반복하여 정렬하는 방법
• 시간 복잡도: 평균 O(NlogN) / 최악 O(n^2)

2. 퀵 정렬 과정

1. 하나를 pivot으로 둔다.
2. pivot보다 작은 값을 low, 큰 값을 high라 둔 뒤, low를 가장 왼쪽에, high를 가장 오른쪽에 둔다.
3. low는 pivot보다 큰 값이 나올 때까지 1씩 증가, high는 pivot보다 작은 값이 나올 때까지 1씩 감소시키며 이동한다.
4. 둘 다 멈추었다면
   1. 둘이 역전되지 않았다면 교환
   2. 둘이 역전되었다면 high에 pviot을 두고 pivot 기준으로 두 배열을 또다시 1~4과정을 반복한다.

• C++로 구현한 퀵정렬

2. 문제 풀어보기