Day-6 퀵 정렬

• 1. 퀵 정렬

• 2. 퀵 정렬 과정

• 3. 예제 문제

---

1. 퀵 정렬

• 기준값(pivot)을 선정해 해당 값을 기준으로 정렬하는 방식이다.
• 기준값 선정 방식이 시간 복잡도에 많은 영향을 준다.
• 평균 시간 복잡도는 O(nlogn)이다.
• pivot을 중심으로 작은 데이터와 큰 데이터로 나누면서 정렬한다.

---

2. 퀵 정렬 과정

1. pivot을 설정
2. pivot을 기준으로 다음 과정을 거쳐 데이터를 2개의 집합으로 분리
   - start가 pivot보다 작으면 start 1 증가
   - end가 pivot보다 크면 end 1 감소
   - start가 pivot보다 크고 end가 pivot보다 작으면, start와 end를 swap하고 start 1 증가, end 1 감소
   - start와 end가 만날 때까지 반복
   - start와 end가 만나면 pivot을 삽입. 만난 지점의 값보다 pivot이 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot을 삽입
3. 분리 집합에서 각각 pivot을 설정
4. 분리 집합이 1개 이하가 될 때까지 1~3을 반복

---

3. 예제 문제

[24090] 알고리즘 수업 - 퀵 정렬 1 (JAVA)