배열을 분할한다는 것은 배열로부터 임의의 수를 가져와(이 수를 피벗이라고 부름) 피벗보다 작은 모든 수는 피벗의 왼쪽에, 피벗보다 큰 모든 수는 피벗의 오른쪽에 두는 것이다. 아래와 같은 배열이 있다고 하자. 일관된 설명을 위해 가장 오른쪽에 있는 값을 항상 피벗으로 하고 3을 이용해 분할해 보자. 두 개의 포인터를 사용해 하나는 배열 가장 왼쪽에 있는 값에, 다른 하나는 가장 오른쪽 있는 값에 할당한다. 분할은 다음의 단계를 따라 실제 분할한다. 왼쪽 포인터를 한 셀씩 계속 오른쪽으로 옮기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다. 오른쪽 포인터를 한 셀씩 계속 왼쪽으로 옮기면서 피벗보다 작거나 같은 값에 도달하면 멈춘다. 왼쪽 포인터와 오른쪽 포인터가 가리키고 있는 값을 교환한다. 두 포인터가 ..
