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

• 컴퓨터 언어에는 대부분 내장 정렬 함수가 있어 사용자가 스스로 구현하는 데 드는 시간과 노력을 아껴준다.
• 컴퓨터 언어 중 대다수가 내부적으로 채택한 정렬 알고리즘은 퀵 정렬(quick sort)이다.
• 퀵 정렬은 재귀를 사용한 알고리즘으로, 그 동작 방식을 알아보며 재귀를 사용해 어떻게 알고리즘의 속도를 향상시키는지 배울 수 있다.
• 퀵 정렬은 매우 빠른 정렬 알고리즘으로 특히 평균 시나리오에서 매우 효율적이다.
• 최악의 시나리오(역순 정렬된 배열)에서는 삽입 정렬이나 선택 정렬과 성능이 유사하나 대부분의 경우에서는 훨씬 빠르다.
• 퀵 정렬은 분할(partitioning)이라는 개념에 기반한다.

1. 분할

• 배열을 분할한다는 것은 배열로부터 임의의 수, 즉 피벗을 가져와 피벗보다 작은 수는 피벗의 왼쪽에, 큰 수는 피벗의 오른쪽에 두는 것이다.
• 피벗은 어떤 값을 가져와도 상관없다. 즉, 배열의 가장 오른쪽의 값을 고르든, 가장 왼쪽의 값을 고르든 상관없다는 뜻이다.
• 분할이 끝나면 피벗 왼쪽의 값은 모두 피벗보다 작고, 오른쪽의 값은 모두 피벗보다 크다.
• 다른 값들은 아직 완전히 정렬되지 않았지만 피벗 자체는 이제 배열 내에서 올바른 위치에 있다.

2. 퀵 정렬

• 퀵 정렬 알고리즘은 분할과 재귀로 이뤄진다.
• 동작 방식은 다음과 같다.

1. 배열을 분할한다. 피벗은 이제 올바른 위치에 있다.
2. 피벗의 양쪽에 있는 하위 배열을 각각 또 다른 배열로 보고 1단계와 2단계를 재귀적으로 반복한다. 즉, 각 하위 배열을 분할하고 각 하위 배열에 있는 피벗의 양쪽에서 더 작아진 하위 배열을 얻는다. 이어서 하위 배열을 다시 분할하는 과정을 반복한다.
3. 하위 배열이 원소를 0개 또는 1개 포함하면 기저 조건이므로 아무것도 하지 않는다.

3. 퀵 정렬의 효율성

• 퀵 정렬의 효율성을 알아내려면 한 번 분할할 때의 효율성을 밝혀야 한다.
• 분할에 필요한 단계를 분류해 보자.
  1. 비교: 각 값과 피벗을 비교한다.
  2. 교환: 적절한 때에 왼쪽과 오른쪽 포인터가 가리키고 있는 값을 교환한다.
• 각 분할마다 배열 내 각 원소를 피벗과 비교하므로 최소 N번 비교한다.
• 그러나 교환 횟수는 데이터가 어떻게 정렬되어 있느냐에 따라 다르다.
• 가능한 값을 모두 교환한다 해도 한 번에 값 두개를 교환하므로 한 분할에서 최대 N/2번 교환한다.
• 대부분의 경우 매 단계마다 교환이 일어나지는 않는다. 무작위로 정렬된 데이터가 있을 때, 일반적으로 대략 값의 반 정도만 교환한다. 즉 평균적으로 N/4번 정도 교환한다.
• 따라서 평균적으로 N번 비교하고, N/4번 교환한다.
• O(N)시간에 분할을 실행한다고 볼 수 있다.
• 이는 한 번 분할할 때의 효율성이다.

3.2 빅 오로 나타낸 퀵 정렬

• 빅 오 표기법 관점에서 퀵 정렬을 어떻게 분류할까?
• 배열의 원소가 N개일 때 퀵 정렬에 필요한 단계 수는 약 N * logN이다.
• 퀵 정렬의 빅 오는 O(NlogN)이다.

4. 퀵 정렬의 최악의 시나리오

• 많은 알고리즘에서 최선의 시나리오는 배열이 이미 정렬되었을 때다.
• 그러나 퀵 정렬에서의 최선의 시나리오는 분할 후 피벗이 하위 배열의 한가운데 있을 때다.
• 퀵 정렬에서의 최악의 시나리오는 피벗이 항상 하위 배열의 정중앙이 아닌 한쪽 끝에 있을 때다.
• 배열이 완전히 오름차순 또는 내림차순일 때 일어날 수 있다.
• 즉, 이미 정렬된 배열은 퀵 정렬의 최악의 시나리오이다.
• 최악의 시나리오에서 퀵 정렬의 효율성은 O(N^2)이다.

✍🏻
빅 오 표기법은 최악의 시나리오의 시간 복잡도를 기준으로 한다는 점을 생각해 보면, 퀵 정렬의 정확한 빅 오는 O(N^2)이다.
그러나 배열의 원소가 N개일 때 이 배열의 원소들이 최악의 시나리오로 정렬되어 있을 확률은 극히 적다.
정확한 확률은 2/N!이다.
따라서 퀵 정렬의 시간 복잡도는 O(N^2)이나, 그 확률이 극히 적으므로 통상적으로 O(NlogN)이라고 표기한다.
퀵 정렬의 효율성을 좀 더 정확히 나타내기 위해서는 빅 세타 표기법을 사용할 수 있다.
Θ(NlogN), O(N^2)

5. 퀵 셀렉트

• 무작위로 정렬된 배열이 있을 때, 정렬은 안 해도 되지만 배열에서 열 번째로 작은 값 혹은 열다섯 번째로 큰 값을 알고 싶다고 하자. 가령 배열의 중간값을 알고 싶을 때 도움이 될 것이다.
• 전체 배열을 정렬한 후 적절한 인덱스를 찾아보면 이 답을 바로 알 수 있다.
• 그러나 퀵 정렬처럼 빠른 정렬을 사용한다 하더라도 평균적으로 O(NlogN)의 시간이 필요하다.
• 이런 방법보다는 퀵 셀렉트(Quick Select)라는 알고리즘을 사용해서 훨씬 더 나은 성능을 낼 수 있다.
• 퀵 셀렉트도 분할에 기반하며, 퀵 정렬과 이진 검색의 하이브리드 정도로 생각할 수 있다.
• 1장에서 살펴봤듯이, 분할이 끝나면 피벗 값은 배열 내 올바른 위치에 있다.
• 퀵 셀렉트는 배열 분할 중 찾으려는 값이 위치한 배열에서만 계속 검색을 이어나간다. 즉, 배열을 계속 반으로 나누되 찾으려는 값이 있을 배열에만 집중한다.
• 버려지는 배열의 원소들은 정렬되지 않는다.
• 퀵 셀렉트의 훌륭한 점 하나는 전체 배열을 정렬하지 않고도 올바른 값을 찾을 수 있다는 것이다.

5.1 퀵 셀렉트의 효율성

• 퀵 셀렉트의 효율성은 평균 시나리오에서 O(N)이다.
• 각 분할이 일어날 때마다 분할 중인 하위 배열에 대해 N단계가 필요하다.
• 원소가 8개인 배열을 생각해 보자. 8, 4, 2, 총 3번의 분할이 필요하다.
• 8 + 4 + 2 = 14로 8의 2배수에 근접하다.
• 원소가 64개인 배열은 64 + 32 + 16 + 8 + 4 + 2 = 126단계가 필요하다.
• 원소가 N개인 배열에 대해 대략 2N 단계가 필요함을 알 수 있다.

6. 다른 알고리즘의 핵심 역할을 하는 정렬

• 현재까지 알려진 가장 빠른 정렬 알고리즘의 속도는 O(NlogN)이다. 퀵 정렬이 가장 유명하지만 다른 알고리즘도 많다.
• 예를 들어 병합 정렬(merge sort)또한 잘 알려진 O(NlogN)알고리즘이다.
• 중요한 점은 가장 빠른 정렬 알고리즘이 O(NlogN)의 시간 복잡도를 갖는다는 사실인데, 이 속도가 다른 알고리즘에도 영향을 미치기 때문이다.
• 많은 알고리즘에서 정렬을 더 큰 프로세스의 일부로 사용한다. 이렇게 함으로써 최소 O(NlogN)의 알고리즘이 된다.

7. 마무리

• 퀵 정렬과 퀵 셀렉트는 골치 아픈 문제를 푸는 효율적인 해결법을 제시하는 재귀 알고리즘이다.
• 이제는 재귀를 이용해 연산하는 자료 구조를 다룰 준비가 되었다.