이번에는 퀵 정렬에 대해서 정리해보려고한다.

퀵 정렬이란?

퀵 정렬은 불안정 정렬이며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 방법이다.

• 불안정 정렬?
  • 정렬 과정에서 같은 값을 가진 요소의 상대적 순서가 보장되지 않는 정렬을 뜻한다.
  • 예를들어, [a1, b, c, a2] 가 있다고 가정하겠다.
    • a1, a2는 같은 a이며, 위 예제에서는 이해하기 쉽도록 a1, a2로 설명하겠다.
  • 정렬이 완료된 후 [a2, a1, b, c] 가 될 수도 있고, [a1, a2, b, c]가 될 수도 있다.
  • 이처럼 정렬 이후 상대적으로 뒤에 있던 a2가 항상 뒤에 오는 것이 아닌 앞으로 올 수도 있기에, 상대적인 순서를 보장하지 못하는 불안정 정렬이라고 불린다.

분할 정복 알고리즘의 하나이며, 배열을 비균등하게 분할하여 정렬을 수행한다.

• 분할 정복 알고리즘?
  • 문제를 작은 하위 문제로 나누고, 각 하위 문제들을 해결한 후 그 결과를 결합하여 원래 문제를 해결하는 접근 방식이다.
  • 보통 아래와 같은 단계를 거치게 되어있다.
    • 분할(Divide): 해결하고자 하는 문제를 더 작은 하위 문제로 분할 한다.
    • 정복(Conquer): 각 하위 문제를 재귀적으로 해결한다. 만약 하위 문제를 더 이상 나눌 수 없다면 해결할 수 있다.
    • 결합(Combine): 하위 문제의 해를 결합하여 원래 문제의 해를 구한다.

평균적으로 빠른 수행 속도를 보장하기에, 주로 사용하는 곳에서 개선된 방법으로 사용되고 있다.

• 알고리즘을 풀면서 흔히 사용하는 Arrays.sort() 는 기본 타입 배열에 대해 듀얼 피벗 퀵정렬을 사용한다.
• 객체 배열에 대해서는 팀정렬 알고리즘을 사용한다.
  • 팀정렬은 병합 정렬 + 삽입 정렬의 장점만을 결합한 알고리즘으로 안정적인 정렬 방법이다.

본 글에서는 일반적인 퀵 정렬과 듀얼 피벗 퀵정렬에 대해 간단하게 알아볼 것이며, 이외에도 주로 사용하는 정렬 기능의 차이와 어떤 방법을 선택하면 좋을 지에 대해서는 아래 글을 참고하면 좋을 것 같다.

[Java] Java의 정렬 알고리즘 - Arrays와 Collections

동작 과정

기본적으로 맨 왼쪽 원소를 **pivot**으로 설정하고, 이를 제외한 맨 왼쪽의 원소를 low, 맨 오른쪽의 원소를 **high**로 설정한다.

이후 조건에 맞춰 **low**를 증가시켜주거나, **high**를 줄여가며 교환하고 마지막에는 **pivot**과 **high**의 위치를 교환하게 된다.

• **pivot**을 기준으로 **array[low]**의 값이 작다면 정렬 대상이 아니니 **low**를 증가시킨다.
  • 반대로 **array[low]**의 값이 크다면 정렬 대상이 되는 것이다.