13 속도를 높이는 재귀 알고리즘

퀵정렬

매우 빠른 정렬 알고리즘이다.

평균 시나리오에서는 훨씬 효율적이다.

최악의 시나리오에서는 삽입정렬, 선택정렬과 성능이 유사하다.

분할

배열로부터 임의의 수를 가져와 (피벗) 피벗보다 작은 수는 왼쪽에, 큰 수는 오른쪽에 두는 것이다.

1. 왼쪽 포인터를 한 셀씩 계속 오른쪽으로 옮기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다.
2. 오른쪽 포인터를 한셀씩 왼쪽으로 옮기면서 피벗보다 작거나 같은 값이 도달하면 멈춘다. (배열 맨 앞에 도달해도 멈춤)
3. 오른쪽 포인터가 멈춘 후에는
   1. 왼쪽포인터가 오른쪽 포인터에 도달하거나 넘어섰으면 4단계로 넘어간다.
   2. 그렇지않으면 왼쪽 포인터와 오른쪽 포인터의 값을 교환 후 1,2,3 단계 반복
4. 끝으로 왼쪽 포인터가 현재 가리키고 있는 값과 피벗을 교환

퀵정렬

퀵 정렬 알고리즘은 분할과 재귀로 이루어진다.

1. 배열을 분할한다.
2. 피벗을 기준으로 왼쪽 오른쪽을 각각의 배열로 보고
   1. 하위 배열을 분할하고 각 하위배열에 있는 피벗의 왼쪽,오른쪽에서 더 작아진 하위배열을 얻는다.
3. 하위배열이 원소를 0개 또는 1개 포함하면 기저조건이므로 아무것도 하지 않는다.

퀵 정렬의 효율성

효율성을 알아내려면 한번 분할할 때의 효율성을 밝혀야한다.

분할에 필요한 단꼐는 두종류이다.

• 비교 : 각 값과 피벗을 교환
• 교환 : 적절한 때에 왼쪽과 오른쪽 포인터의 값을 교환

13.5 퀵 셀렉트 전체 배열을 정렬하지 않고 올바른 값을 찾을수 있다.

13.6 다른 알고리즘의 핵심 역할을 하는 정렬 현재까지 알려진 가장 빠른 정렬 알고리즘의 속도는 O(NlogN)이다. 퀵 정렬이 가장 유명하고 병합 정렬또한 잘알려진 알고리즘이다. 가장 빠른 정렬 알고리즘이 O(NlogN)인데, 이는 다른 알고리즘에도 영향을 준다. 많은 알고리즘에서 정렬을 더 큰 프로세스의 일부로 사용한다.

13.7 마무리 퀵 정렬과 퀵 셀렉트는 효율적인 해결법을 제시하는 재귀 알고리즘이다.