정렬 알고리즘 #2 - 퀵 정렬(quick sort), 병합 정렬(merge sort), 이진탐색(binary search)

1. 퀵 정렬(quick sort)
다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
분할 정복 알고리즘의 하나로 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다.

- 시간 복잡성
best-case : O(n lg n) [lg(n)은 log₂(n)의 줄인 표현]
average-case : O(n lg n)
worst-case: O(n²)

- Java 코드

2. 병합 정렬(merge sort)
분할 정복 알고리즘의 하나로, 나뉘어지지 않을 때까지 리스트를 분할한 뒤 하위 리스트를 정렬한 후 각가을 하나로 합친다.

- 시작 복잡성
best-case : O(n lg n) [lg(n)은 log₂(n)의 줄인 표현]
average-case : O(n lg n)
worst-case: O(n lg n)

- Java 코드

3. 이진 탐색(binary search)
리스트가 정렬되어 있지 않으면 검색 시 주어진 값에 맞는 원소를 찾기 위해 리스트를 모두 찾아봐야 한다. 하지만 정렬된 리스트가 있거나 검색하기 전에 정렬을 수행한 상황이라면 리스트에서 값을 찾을 때 이진 검색을 사용하는 것이 매우 효율적인 방법이다.
43억개의 원소가 있는 리스트에서 특정 값을 찾아낼 때 최악의 탐색 깊이는 32회이다.

- 시간 복잡성
best-case : O(lg n) [lg(n)은 log₂(n)의 줄인 표현]
average-case : O(lg n)
worst-case : O(lg n)

- Java 코드