• 퀵 정렬은 합병 정렬 ( Merge Sort ) 와 마찬가지로 배열을 둘 씩 분할하여 정렬하는 방식입니다.

  • 퀵 정렬은 동일한 배열 내에서 자리를 이동 시킵니다. pivot 의 값을 정하고 pivot 값을 기준으로 분할하여 정렬을 진행 합니다.
  • 한 번 위치가 결정된 pivot 값은 이후 연산에서는 해당 값을 제외하고 연산을 진행하기 때문에 정렬이 진행 될 수록, 즉 분할이 점점 진행 될 수도록 계산해야 할 데이터의 수가 점점 줄어드는 특성이 있습니다.

• 즉, 퀵 정렬은 양 끝에서 피벗을 기준으로 피벗보다 작은 값을 갖는 위치에 있어야 할 원소가 피벗보다 크거나, 그 반대인 경우 서로 원소를 교환하는 방식이다.

• 시간 복잡도 평균적으로 O(n log n) 을 가집니다. 합병 정렬도 O(n log n) 시간복잡도를 가지지만 실제 정렬에서 합병 정렬보다 훨씬 빠른 시간 안에 정렬이 가능 합니다.

  

• 퀵 정렬은 분할 정복( Divide and Conquer ) 방식으로 진행 됩니다.

  • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
  • 순환 ( 재귀 ) 호출을 이용하여 구현 합니다.

• 퀵 정렬은 불안정 정렬이며, 다른 원소와 비교만으로 정렬을 수행하는 비교 정렬에 속합니다.

• 추가적으로 자바에서는 primitive 타입 배열들의 경우 dual-pivot quick sort 을 기본 정렬로 사용합니다.

퀵 정렬