[Algorithm] 정렬 알고리즘(퀵)

---

퀵 정렬(Quick)

: 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.

---

퀵 정렬의 특징

---

• 가장 많이 사용된다.
• 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 된다.
• 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.

---

퀵 정렬 동작 예시

---

Step 0 : 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '9'가 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다.

Step 1 : 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '0'이 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다.

Step 2 : 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '6'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '0'이 선택된다. 단, 이처럼 위치가 엇갈리는 경우 '피벗'과 '작은 데이터'의 위치를 서로 변경한다.

Step 3 : 이제 분할이 완료 되었다. 이제 '5'의 왼쪽 데이터는 모두 5보다 작고, 오른쪽 데이터는 모두 '5'보다 크게 된다. 이렇게 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할이라고 한다.

Step 4 : 왼쪽 데이터 묶음에 대해서도 마찬가지로 퀵 정렬을 수행한다. 현재 피벗 값은 '0'인데 가장 작은 값이기 때문에 그대로 두고 그 다음 값인 '3'을 피벗 값으로 두고 수행한다.

 

퀵 정렬의 시간 복잡도