• 분할 정복(divide and conquer)를 통해 정렬함.
• 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬임.
• 불안정 정렬임.

알고리즘

• 배열에서 하나의 원소를 고름. 이렇게 고른 원소는 피벗(pivot)이라고함.
• 피벗 기준으로 앞에는 피벗보다 값이 작은 원소, 뒤는 피벗보다 값이 큰 원소를 둘로 나눔.
  • 이렇게 나누는 걸 분할이라고함.
    • 왼쪽 끝과 오른쪽 끝에서 움직이면서 만날 때 새로운 피벗을 정함.
      • 새로운 피벗을 정하는 것 → 재귀
• 분할된 두 개의 배열에 대해서 재귀적으로 위 과정을 반복함.
  • 재귀는 배열의 크기가 0, 1이 될 때까지 반복.
• 재귀 호출이 한번 징행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해짐.

예시

5 - 3 - 7 - 6 - 2 - 1 - 4 
i                   j   p

• 피벗은 4 배열 왼쪽에 있는 i 위치의 값이 피벗 보다 크고, j위치의 값은 피벗보다 작음.
  • 좌측은 피벗보다 작은 값이 들어가고 우측은 큰 값이 들어가야 하기 때문에 둘을 스왑함.

1 - 3 - 7 - 6 - 2 - 5 - 4 
    i           j       p

• j 위치의 값이 피벗 값보다 작지만, i의 위치도 피벗값보다 작으므로 교환하지 않음.
• i와 j의 위치를 ++, — 이동해주면서 위와 같은 연산을 반복함.
• i위치를 피벗값 보다 큰 값이 나올 때까지 진행해 j의 위치의 값과 교환함.

1 - 3 - 2 - 6 - 7 - 5 - 4 
        i       j       p

1 - 3 - 2 - 4 - 7 - 5 - 6 
            p

• i의 위치가 j의 위치보다 커지면 피벗 값을 교환함.

1 - 3 - 2       7 - 5 - 6
1 - 2 - 3       5 - 6 - 7

• 좌, 우의 리스트에 대해 각각 퀵 정렬을 재귀적으로 수행함.

소스코드 - Kotlin