퀵 정렬

퀵 정렬 (Quick Sort)

특징

• C++ Algorithm 라이브러리에서 sort()를 통해 사용할 수 있다.
• 피벗을 기준으로 큰 값, 작은 값을 교체한다.
• 완전 이진 트리와 흡사한 형태를 가진다.

퀵정렬을 통한 오름차순 구현

순서

• 피벗 : 가장 왼쪽에 위치한 값이라 가정
• start : 피벗 다음에 위치한 값
• end : 가장 오른쪽에 위치한 값

  1. start : 앞에서부터 뒤로 이동하며 피벗보다 큰 값을 찾음
  2. end : 뒤에서 앞으로 이동하며 피벗보다 작은 값을 찾음
  3. start와 end가 엇갈리는 시점에서 작은 값과 피벗을 교체함
  4. 피벗을 기준으로 왼쪽, 오른쪽에서 다시 퀵정렬을 수행한다.