알고리즘 중에 분할 정복 알고리즘(divide and conquer algorithm)이 있습니다. 어려운 문제를 작게 쪼개서(divide) 해결해 나가는(conquer) 것을 말합니다. 이번에는 대표적인 분할 정복 알고리즘인 퀵 정렬(Quicksort)에 대해 알아보겠습니다.

그림 15-10을 볼까요?

그림 15-10 퀵 정렬 ①

pivot은 정렬되지 않은 리스트에서 가운데 위치한 인덱스의 데이터를 말합니다. 주의할 점은 인덱스가 아니라 데이터라는 것입니다. start는 첫 번째 인덱스고 end는 마지막 인덱스입니다. left와 right는 각각 start와 end를 가리킵니다.

left 인덱스는 오른쪽으로 이동하고 right 인덱스는 왼쪽으로 이동합니다. 목적은 pivot을 기준으로 왼쪽은 pivot보다 작은 데이터가 모이고, 오른쪽은 큰 데이터가 모이도록 만드는 것입니다. 그렇게 하려면 left는 오른쪽으로 이동하다가 pivot보다 큰 데이터를 만나면 멈춥니다. right는 왼쪽으로 이동하다가 pivot보다 작은 데이터를 만나면 멈춥니다. 그리고 두 데이터를 교환합니다.